BZOJ 2243: [SDOI2011]染色 [树链剖分+细节]【数据结构】

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2243
————————————————————————————————————————————————
2243: [SDOI2011]染色

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 7492 Solved: 2803
[Submit][Status][discuss]
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]之间。

Source

第一轮day1

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

在树上两点间的路上进行修改 那么就是树链剖分，
根据操作 是区间染色 所以要用线段树维护

注意在维护的时候线段树上的每个点要多维护一个最左边和最右边的颜色。
方便合并的时候计算颜色个数

然后就是注意颜色可能为0
lazy标记的时候改成-1， 习惯性的用0 WA到死啊。

附本题代码

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

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+7;

/***************************************/

int n,m;
int c[N];
vector<int >G[N];

int fa[N],sz[N],son[N],dep[N];

int dfs1(int u,int f,int d){
    fa[u]=f,sz[u]=1,son[u]=0,dep[u]=d;
    int gz = G[u].size();
    for(int to,i=0;i<gz;i++){
        to = G[u][i];
        if(to==f) continue;
        dfs1(to,u,d+1);
        sz[u]+=sz[to];
        if(sz[son[u]]<sz[to]) son[u]=to;
    }
}

int top[N],tree[N],pre[N],cnt;

int dfs2(int u,int tp){
    top[u]=tp,tree[u]=++cnt,pre[tree[u]]=u;
    if(son[u]) dfs2(son[u],tp);
    int gz = G[u].size();
    for(int to,i=0;i<gz;i++){
        to = G[u][i];
        if(to==fa[u]||to==son[u])continue;
        dfs2(to,to);
    }
}

int sum[N<<2],lazy[N<<2],lc[N<<2],rc[N<<2];

void pushup(int rt){
    sum[rt] = sum[rt<<1]+sum[rt<<1|1]-(rc[rt<<1] == lc[rt<<1|1]);
    lc[rt]=lc[rt<<1],rc[rt]=rc[rt<<1|1];
}

void pushdown(int rt){
    if(lazy[rt]!=-1){
        lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
        sum [rt<<1] = sum [rt<<1|1] = 1;
        lc[rt<<1]   = rc[rt<<1]   = lazy[rt];
        lc[rt<<1|1] = rc[rt<<1|1] = lazy[rt];
        lazy[rt]=-1;
    }
}

void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=1,rc[rt]=lc[rt]=c[pre[l]];
        return ;
    }
    int m = (r+l)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}

void update(int rt,int r,int L,int R,int clr){
    if(L<=l&&r<=R){
        rc[rt]=lc[rt]=lazy[rt]=clr;
        sum[rt] = 1;
        return ;
    }
    pushdown(rt);
    int m = (r+l)>>1;
    if(L<=m) update(rt<<1,m,L,R,clr);
    if(R> m) update(rt<<1|1,r,clr);
    pushup(rt);
    return ;
}

int query(int rt,int R){
    if(L>R) return 0;
    if(L<=l&&r<=R) return sum[rt];
    pushdown(rt);
    int ans = 0,m = (r+l)>>1;
    if(R<=m)      ans = query(rt<<1,R);
    else if(L>m)  ans = query(rt<<1|1,R);
    else          ans = query(rt<<1,R)+
                        query(rt<<1|1,R)-
                        (rc[rt<<1]==lc[rt<<1|1]);
    pushup(rt);
    return ans;
}

int query_color(int rt,int pos){
    if(l==r)  return lc[rt];
    pushdown(rt);
    int m = (r+l)>>1,ans;
    if(pos<=m) ans = query_color(rt<<1,pos);
    else       ans = query_color(rt<<1|1,pos);
    pushup(rt);
    return ans;
}

void init(){
    cnt = 0;
    for(int i=1;i<=n;i++)G[i].clear();
    memset(sum,0,sizeof(sum));
    memset(lazy,-1,sizeof(lazy));
};

void brush(int x,int y,int clr){
    int fx = top[x],fy = top[y];
    while(fx!=fy){
        if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
        update(1,1,n,tree[fx],tree[x],clr);
        x = fa[fx],fx = top[x];
    }
    if(tree[x]>tree[y]) swap(x,y);
    update(1,tree[y],clr);
    return ;
}

void solve(int x,int y){
    int fx = top[x],fy = top[y];
    int ans = 0;
    while(fx!=fy){
        if(dep[fx]<dep[fy]) swap(fx,y);
        ans += query(1,tree[x]);
        if(query_color(1,tree[fa[fx]]) == query_color(1,tree[fx])) ans--;
        x = fa[fx],y);
    ans += query(1,tree[y]);
    printf("%d\n",ans);
    return ;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        init();

        for(int i=1;i<=n;i++) scanf("%d",&c[i]);

        for(int i=2,v;i<=n;i++){
            scanf("%d %d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }

        dfs1(1,1);
        dfs2(1,1);
        build(1,n);

        int l,x;
        char a[10];
        while(m--){
            scanf("%s",a);
            scanf("%d %d",&l,&r);
            if(a[0]=='C'){
                scanf("%d",&x);
                brush(l,x);
            }
            else  solve(l,r);
        }
    }
    return 0;
}