2243: [SDOI2011]染色（LCT）

2243: [SDOI2011]染色

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 10909 Solved: 4216
[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

思路：可以用树剖做。在线段树上维护区间颜色种数，最左边的颜色，最右边的颜色，加lazy标记...然后可以搞了。

这里用LCT做，加深下自己对LCT的理解。

之前有道题，树上DP，但是树的形态是变化的，因为对LCT理解不深，不知道最后没写出来。写了这题，估计可以写了。

我们用lcol表示原树上儿子（只考虑当前重链）颜色，rcol原树上父亲颜色。这样就可以上推了。

void pushup(int x)
{
    lcol[x]=ch[x][0]?lcol[ch[x][0]]:col[x];
    rcol[x]=ch[x][1]?rcol[ch[x][1]]:col[x];
    sum[x]=1;
    if(ch[x][0]) sum[x]+=sum[ch[x][0]]-(col[x]==rcol[ch[x][0]]);
    if(ch[x][1]) sum[x]+=sum[ch[x][1]]-(col[x]==lcol[ch[x][1]]);
}

注意rev操作，不仅仅要交换左右儿子，也要交换lcol和rcol，这里wa了一下下。其他部分都是常规操作。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
int ch[maxn][2],fa[maxn],rev[maxn],sum[maxn],col[maxn],lcol[maxn],rcol[maxn];
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],lazy[maxn],cnt;
void reverse(int x){ if(!x) return ; swap(ch[x][0],ch[x][1]);swap(lcol[x],rcol[x]); rev[x]^=1;} //一定要记得把lcol和rcol给swap了...
void change(int x,int y){ col[x]=lcol[x]=rcol[x]=y; sum[x]=1; lazy[x]=y;}
void pushdown(int x)
{
    if(rev[x]){
        reverse(ch[x][0]); reverse(ch[x][1]); rev[x]=0;
    }
    if(lazy[x]){
        change(ch[x][0],lazy[x]);
        change(ch[x][1],lazy[x]);
        lazy[x]=0;
    }
}
void pushup(int x)
{
    lcol[x]=ch[x][0]?lcol[ch[x][0]]:col[x];
    rcol[x]=ch[x][1]?rcol[ch[x][1]]:col[x];
    sum[x]=1;
    if(ch[x][0]) sum[x]+=sum[ch[x][0]]-(col[x]==rcol[ch[x][0]]);
    if(ch[x][1]) sum[x]+=sum[ch[x][1]]-(col[x]==lcol[ch[x][1]]);
}
void add(int u,int v){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; }
void dfs(int u,int f)
{
    fa[u]=f; for(int i=Laxt[u];i;i=Next[i]) if(To[i]!=f) dfs(To[i],u);
}
int get(int x){ return ch[fa[x]][1]==x;}
int isroot(int x){ return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}
void rotate(int x)
{
    int old=fa[x],fold=fa[old],opt=get(x);
    if(!isroot(old)) ch[fold][get(old)]=x;
    fa[x]=fold; fa[old]=x; fa[ch[x][opt^1]]=old;
    ch[old][opt]=ch[x][opt^1]; ch[x][opt^1]=old;
    pushup(old); //x最后一次性pushup，不必重复updatex
}
void P(int x){ if(!isroot(x)) P(fa[x]); pushdown(x);}
void splay(int x)
{
    P(x); for(int f;!isroot(x);rotate(x)){
        if(!isroot(f=fa[x])) rotate(get(x)==get(f)?f:x);
    } 
    pushup(x);
}
void access(int x)
{
    for(int y=0;x;y=x,x=fa[x]){
        splay(x); ch[x][1]=y; pushup(x);//!要的
    }
}
void makeroot(int x) { access(x); splay(x); reverse(x);}
int main()
{
    int N,M,u,v,c; char opt[4];
    scanf("%d%d",&N,&M);
    rep(i,1,N) scanf("%d",&col[i]),change(i,col[i]);
    rep(i,1,N-1){
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0);
    while(M--){
        scanf("%s",opt+1);
        if(opt[1]=='Q'){
            scanf("%d%d",&u,&v);
            makeroot(u); access(v); splay(v);
            printf("%d
",sum[v]);
        }
        else {
            scanf("%d%d%d",&u,&v,&c);
            makeroot(u); access(v); splay(v);
            change(v,c);
        }
    }
    return 0;
}