BZOJ2243：[SDOI2011]染色—

http://www.lydsy.com/JudgeOnline/problem.php?id=2243

Description

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），

如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

3
1
2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

————————————————————————————————

（吐槽一下BZOJ，洛谷能过的代码BZOJ RE……后来优化了读入才AC……坑爹啊）

首先是树链剖分的裸题。点这里看树链剖分原理。

然后考虑合并区间时候的问题。

我们记录每个区间的端点颜色，区间个数，当然还有lazy标记。

然后区间合并看相邻的端点颜色是否一致，如果一致答案就-1。

树上需要特意查重路径的顶点和他爸颜色是否一致，如果一致答案就-1。

#include<cstdio>

#include<iostream>

using namespace std;

const int N=;

int read(){

    int X=,w=;char ch=;

    while(ch<''||ch>''){w|=ch=='-';ch=getchar();}

    while(ch>=''&&ch<='')X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to;

    int nxt;

}edge[*N];

struct tree{

    int lc;

    int rc;

    int num;

    int lazy;

}t[*N];

int head[N],cnt=,n;

void add(int u,int v){

    cnt++;

    edge[cnt].to=v;

    edge[cnt].nxt=head[u];

    head[u]=cnt;

    return;

}

int fa[N],dep[N],size[N],son[N],top[N],pos[N],idx[N];

int val[N];

void dfs1(int u){

    size[u]=;

    for(int i=head[u];i;i=edge[i].nxt){

    int v=edge[i].to;

    if(v==fa[u])continue;

    fa[v]=u;dep[v]=dep[u]+;

    dfs1(v);

    size[u]+=size[v];

    if(!son[u]||size[v]>size[son[u]])son[u]=v;

    }

    return;

}

int tot;

void dfs2(int u,int anc){

    tot++;

    pos[u]=tot;

    idx[tot]=u;

    top[u]=anc;

    if(!son[u])return;

    dfs2(son[u],anc);

    for(int i=head[u];i;i=edge[i].nxt){

    int v=edge[i].to;

    if(v==fa[u]||v==son[u])continue;

    dfs2(v,v);

    }

    return;

}

void init(){

    dfs1();

    top[]=idx[]=pos[]=;

    tot=;

    dfs2(,);

    return;

}

void pushdown(int a){

    if(t[a].lazy!=-){

    t[a*].lazy=t[a*+].lazy=t[a].lazy;

    t[a*].lc=t[a*].rc=t[a].lazy;

    t[a*+].lc=t[a*+].rc=t[a].lazy;

    t[a*].num=t[a*+].num=;

    t[a].lazy=-;

    }

    return;

}

void build(int a,int l,int r){

    t[a].lazy=-;

    if(l==r){

    t[a].lc=val[idx[l]];

    t[a].rc=val[idx[l]];

    t[a].num=;

    return;

    }

    int mid=(l+r)>>;

    build(a*,l,mid);

    build(a*+,mid+,r);

    t[a].lc=t[a*].lc;t[a].rc=t[a*+].rc;

    t[a].num=t[a*].num+t[a*+].num;

    if(t[a*].rc==t[a*+].lc)t[a].num--;

    return;

}

int query(int a,int l,int r,int l1,int r1){

    if(r1<l||l1>r)return ;

    if(l1<=l&&r<=r1){

    return t[a].num;

    }

    int mid=(l+r)>>;

    pushdown(a);

    int k1=query(a*,l,mid,l1,r1);

    int k2=query(a*+,mid+,r,l1,r1);

    if(k1&&k2){

    if(t[a*].rc==t[a*+].lc)k1--;

    }

    return k1+k2;

}

int check(int a,int l,int r,int k){

    if(l==r)return t[a].lc;

    int mid=(l+r)>>;

    pushdown(a);

    if(l<=k&&k<=mid)return check(a*,l,mid,k);

    else if(mid<k&&k<=r)return check(a*+,mid+,r,k);

}

int pathquery(int u,int v){

    int res=;

    while(top[u]!=top[v]){

    if(dep[top[u]]<dep[top[v]]){int t=u;u=v;v=t;}

    int ans=query(,,n,pos[top[u]],pos[u]);

    if(check(,,n,pos[top[u]])==check(,,n,pos[fa[top[u]]]))ans--;

    res+=ans;

    u=fa[top[u]];

    }

    if(dep[u]>dep[v]){int t=u;u=v;v=t;}

    return res+query(,,n,pos[u],pos[v]);

}

void modify(int a,int l,int r,int l1,int r1,int v){

    if(r1<l||r<l1)return;

    if(l1<=l&&r<=r1){

    t[a].lazy=v;

    t[a].lc=v;t[a].rc=v;

    t[a].num=;

    return;

    }

    int mid=(l+r)>>;

    pushdown(a);

    modify(a*,l,mid,l1,r1,v);

    modify(a*+,mid+,r,l1,r1,v);

    t[a].lc=t[a*].lc;t[a].rc=t[a*+].rc;

    t[a].num=t[a*].num+t[a*+].num;

    if(t[a*].rc==t[a*+].lc)t[a].num--;

    return;

}

void pathmodify(int u,int v,int c){

    while(top[u]!=top[v]){

    if(dep[top[u]]<dep[top[v]]){int t=u;u=v;v=t;}

    modify(,,n,pos[top[u]],pos[u],c);

    u=fa[top[u]];

    }

    if(dep[u]>dep[v]){int t=u;u=v;v=t;}

    modify(,,n,pos[u],pos[v],c);

    return;

}

int main(){

    n=read();int q=read();

    for(int i=;i<=n;i++)val[i]=read();

    for(int i=;i<=n;i++){

    int u=read();

    int v=read();

    add(u,v);

    add(v,u);

    }

    init();

    build(,,n);

    while(q--){

    char op=;

    while(op!='C'&&op!='Q')op=getchar();

    if(op=='C'){

        int a=read();

        int b=read();

        int c=read();

        pathmodify(a,b,c);

    }else{

        int a=read();

        int b=read();

        printf("%d\n",pathquery(a,b));

    }

    }

    return ;

}

巴特西

BZOJ2243：[SDOI2011]染色——题解