BZOJ2243: [SDOI2011]染色（树链剖分/LCT）

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

解题思路：

1.树链剖分：

只修改链，不修改关系，树链剖分。

线段树维护树链剖分序。

时间复杂度O(nlogn²)

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lll spc<<1
  5 #define rrr spc<<1|1
  6 using std::min;
  7 using std::max;
  8 using std::swap;
  9 struct trnt{
 10     int lc;
 11     int rc;
 12     int lzt;
 13     int val;
 14 }tr[1000000];
 15 struct pnt{
 16     int hd;
 17     int col;
 18     int mxs;
 19     int ind;
 20     int fa;
 21     int tp;
 22     int wgt;
 23     int dp;
 24 }p[1000000];
 25 struct ent{
 26     int twd;
 27     int lst;
 28 }e[1000000];
 29 struct bag{
 30     int cl;
 31     int cr;
 32     int vl;
 33     bag friend operator + (bag a,bag b)
 34     {
 35         if(!a.cl)
 36             a.cl=b.cl;
 37         if(!b.cr)
 38             b.cr=a.cr;
 39         return (bag){a.cl,b.cr,(a.vl+b.vl-(a.cr==b.cl)<0)?0:(a.vl+b.vl-(a.cr==b.cl))};
 40     }
 41 };
 42 int n,m;
 43 int cnt;
 44 int dfn;
 45 char cmd[10];
 46 void ade(int f,int t)
 47 {
 48     cnt++;
 49     e[cnt].twd=t;
 50     e[cnt].lst=p[f].hd;
 51     p[f].hd=cnt;
 52     return ;
 53 }
 54 void pushup(int spc)
 55 {
 56     tr[spc].lc=tr[lll].lc;
 57     tr[spc].rc=tr[rrr].rc;
 58     tr[spc].val=tr[lll].val+tr[rrr].val-(tr[lll].rc==tr[rrr].lc);
 59     return ;
 60 }
 61 void chg(int spc,int v)
 62 {
 63     tr[spc].val=1;
 64     tr[spc].lc=tr[spc].rc=v;
 65     tr[spc].lzt=v;
 66     return ;
 67 }
 68 void pushdown(int spc)
 69 {
 70     if(tr[spc].lzt)
 71     {
 72         chg(lll,tr[spc].lzt);
 73         chg(rrr,tr[spc].lzt);
 74         tr[spc].lzt=0;
 75     }
 76     return ;
 77 }
 78 void build(int l,int r,int pos,int spc,int v)
 79 {
 80     if(l==r)
 81     {
 82         tr[spc].lc=tr[spc].rc=v;
 83         tr[spc].val=1;
 84         tr[spc].lzt=0;
 85         return ;
 86     }
 87     int mid=(l+r)>>1;
 88     if(pos<=mid)
 89         build(l,mid,pos,lll,v);
 90     else
 91         build(mid+1,r,pos,rrr,v);
 92     pushup(spc);
 93     return ;
 94 }
 95 void Basic_dfs(int x,int f)
 96 {
 97     p[x].dp=p[f].dp+1;
 98     p[x].fa=f;
 99     int maxs=-1;
100     p[x].wgt=1;
101     for(int i=p[x].hd;i;i=e[i].lst)
102     {
103         int to=e[i].twd;
104         if(to==f)
105             continue;
106         Basic_dfs(to,x);
107         p[x].wgt+=p[to].wgt;
108         if(p[to].wgt>maxs)
109         {
110             maxs=p[to].wgt;
111             p[x].mxs=to;
112         }
113     }
114     return ;
115 }
116 void Build_dfs(int x,int tpl)
117 {
118     if(!x)
119         return ;
120     p[x].tp=tpl;
121     p[x].ind=++dfn;
122     build(1,n,dfn,1,p[x].col);
123     Build_dfs(p[x].mxs,tpl);
124     for(int i=p[x].hd;i;i=e[i].lst)
125     {
126         int to=e[i].twd;
127         if(p[to].ind)
128             continue;
129         Build_dfs(to,to);
130     }
131 }
132 void update(int l,int r,int ll,int rr,int spc,int v)
133 {
134     if(ll>rr)
135         return ;
136     if(l>rr||ll>r)
137         return ;
138     pushdown(spc);
139     if(ll<=l&&r<=rr)
140     {
141         chg(spc,v);
142         return ;
143     }
144     int mid=(l+r)>>1;
145     update(l,mid,ll,rr,lll,v);
146     update(mid+1,r,ll,rr,rrr,v);
147     pushup(spc);
148     return ;
149 }
150 bag mk(int a,int b,int c)
151 {
152     return (bag){a,b,c};
153 }
154 bag ask(int l,int r,int ll,int rr,int spc)
155 {
156     if(l>rr||ll>r)
157         return mk(0,0,0);
158     pushdown(spc);
159     if(ll<=l&&r<=rr)
160         return mk(tr[spc].lc,tr[spc].rc,tr[spc].val);
161     int mid=(l+r)>>1;
162     return ask(l,mid,ll,rr,lll)+ask(mid+1,r,ll,rr,rrr);
163 }
164 int lca(int x,int y)
165 {
166     while(p[x].tp!=p[y].tp)
167     {
168         if(p[p[x].tp].dp<p[p[y].tp].dp)
169             swap(x,y);
170         x=p[p[x].tp].fa;
171     }
172     if(p[x].dp>p[y].dp)
173         swap(x,y);
174     return x;
175 }
176 void rvs(bag &a)
177 {
178     swap(a.cl,a.cr);
179     return ;
180 }
181 int main()
182 {
183     scanf("%d%d",&n,&m);
184     for(int i=1;i<=n;i++)
185         scanf("%d",&p[i].col);
186     for(int i=1;i<n;i++)
187     {
188         int a,b;
189         scanf("%d%d",&a,&b);
190         ade(a,b);
191         ade(b,a);
192     }
193     Basic_dfs(1,0);
194     Build_dfs(1,1);
195     while(m--)
196     {
197         scanf("%s",cmd);
198         if(cmd[0]=='C')
199         {
200             int a,b,c;
201             scanf("%d%d%d",&a,&b,&c);
202             int f=lca(a,b);
203             while(p[a].tp!=p[f].tp)
204             {
205                 update(1,dfn,p[p[a].tp].ind,p[a].ind,1,c);
206                 a=p[p[a].tp].fa;
207             }
208             update(1,dfn,p[f].ind,p[a].ind,1,c);
209             a=b;
210             while(p[a].tp!=p[f].tp)
211             {
212                 update(1,dfn,p[p[a].tp].ind,p[a].ind,1,c);
213                 a=p[p[a].tp].fa;
214             }
215             update(1,dfn,p[f].ind,p[a].ind,1,c);
216         }
217         if(cmd[0]=='Q')
218         {
219             int a,b;
220             
221             scanf("%d%d",&a,&b);
222             int f=lca(a,b);
223             bag ans=(bag){0,0,0};
224             while(p[a].tp!=p[f].tp)
225             {
226                 ans=ask(1,dfn,p[p[a].tp].ind,p[a].ind,1)+ans;
227                 a=p[p[a].tp].fa;
228             }
229             if(a!=f)
230                 ans=ask(1,dfn,p[f].ind+1,p[a].ind,1)+ans;
231             bag ams=(bag){0,0,0};
232             a=b;
233             while(p[a].tp!=p[f].tp)
234             {
235                 ams=ask(1,dfn,p[p[a].tp].ind,p[a].ind,1)+ams;
236                 a=p[p[a].tp].fa;
237             }
238             if(a!=f)
239                 ams=ask(1,dfn,p[f].ind+1,p[a].ind,1)+ams;
240             ans=ask(1,dfn,p[f].ind,p[f].ind,1)+ans;
241             rvs(ans);
242             ans=ans+ams;
243             printf("%d
",ans.vl);
244         }
245     }
246     return 0;
247 }

2.LCT：

比较板子了。

每次维护左侧颜色和右侧颜色（注意特判0节点值）

反转时要反转左右颜色。

路径提取一下输出答案就好了。

时间复杂度O(nlogn)理论上比树剖快

但是：

蒟蒻的我：splay常数居然比logn大

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lll tr[spc].ch[0]
  5 #define rrr tr[spc].ch[1]
  6 #define ls ch[0]
  7 #define rs ch[1]
  8 using std::swap;
  9 struct trnt{
 10     int ch[2];
 11     int fa;
 12     int lzt;
 13     int chg;
 14     int sum;
 15     int val;
 16     int lc;
 17     int rc;
 18     int wgt;
 19     bool anc;
 20 }tr[1000000];
 21 int n,m;
 22 char cmd[10];
 23 bool whc(int spc)
 24 {
 25     return tr[tr[spc].fa].rs==spc;
 26 }
 27 void pushup(int spc)
 28 {
 29     tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+1;
 30     tr[spc].sum=tr[lll].sum+tr[rrr].sum+1-(tr[lll].rc==tr[spc].val)-(tr[rrr].lc==tr[spc].val);
 31     tr[spc].lc=tr[lll].lc?tr[lll].lc:tr[spc].val;
 32     tr[spc].rc=tr[rrr].rc?tr[rrr].rc:tr[spc].val;
 33     return ;
 34 }
 35 void trr(int spc)
 36 {
 37     if(!spc)
 38         return ;
 39     swap(lll,rrr);
 40     swap(tr[spc].lc,tr[spc].rc);
 41     tr[spc].lzt^=1;
 42     return ;
 43 }
 44 void upd(int spc,int v)
 45 {
 46     if(!spc)
 47         return ;
 48     tr[spc].val=tr[spc].lc=tr[spc].rc=v;
 49     tr[spc].sum=1;
 50     tr[spc].chg=v;
 51     return ;
 52 }
 53 void pushdown(int spc)
 54 {
 55     if(tr[spc].lzt)
 56     {
 57         trr(lll);
 58         trr(rrr);
 59         tr[spc].lzt=0;
 60     }
 61     if(tr[spc].chg)
 62     {
 63         upd(lll,tr[spc].chg);
 64         upd(rrr,tr[spc].chg);
 65         tr[spc].chg=0;
 66     }
 67     return ;
 68 }
 69 void recal(int spc)
 70 {
 71     if(!tr[spc].anc)
 72         recal(tr[spc].fa);
 73     pushdown(spc);
 74     return ;
 75 }
 76 void rotate(int spc)
 77 {
 78     int f=tr[spc].fa;
 79     bool k=whc(spc);
 80     tr[f].ch[k]=tr[spc].ch[!k];
 81     tr[spc].ch[!k]=f;
 82     if(tr[f].anc)
 83     {
 84         tr[spc].anc=1;
 85         tr[f].anc=0;
 86     }else
 87         tr[tr[f].fa].ch[whc(f)]=spc;
 88     tr[spc].fa=tr[f].fa;
 89     tr[f].fa=spc;
 90     tr[tr[f].ch[k]].fa=f;
 91     pushup(f);
 92     pushup(spc);
 93     return ;
 94 }
 95 void splay(int spc)
 96 {
 97     recal(spc);
 98     while(!tr[spc].anc)
 99     {
100         int f=tr[spc].fa;
101         if(tr[f].anc)
102         {
103             rotate(spc);
104             return ;
105         }
106         if(whc(spc)^whc(f))
107             rotate(spc);
108         else
109             rotate(f);
110         rotate(spc);
111     }
112     return ;
113 }
114 void access(int spc)
115 {
116     int lst=0;
117     while(spc)
118     {
119         splay(spc);
120         tr[rrr].anc=1;
121         tr[lst].anc=0;
122         rrr=lst;
123         pushup(spc);
124         lst=spc;
125         spc=tr[spc].fa;
126     }
127     return ;
128 }
129 void Mtr(int spc)
130 {
131     access(spc);
132     splay(spc);
133     trr(spc);
134     return ;
135 }
136 void split(int x,int y)
137 {
138     Mtr(x);
139     access(y);
140     splay(y);
141     return ;
142 }
143 void link(int x,int y)
144 {
145     Mtr(x);
146     tr[x].fa=y;
147     return;
148 }
149 int main()
150 {
151     scanf("%d%d",&n,&m);
152     for(int i=1;i<=n;i++)
153     {
154         tr[i].anc=1;
155         scanf("%d",&tr[i].val);
156         tr[i].lc=tr[i].rc=tr[i].val;
157     }
158     for(int i=1;i<n;i++)
159     {
160         int a,b;
161         scanf("%d%d",&a,&b);
162         link(a,b);
163     }
164     while(m--)
165     {
166         scanf("%s",cmd);
167         if(cmd[0]=='Q')
168         {
169             int a,b;
170             scanf("%d%d",&a,&b);
171             split(a,b);
172             printf("%d
",tr[b].sum);
173         }else{
174             int a,b,c;
175             scanf("%d%d%d",&a,&b,&c);
176             split(a,b);
177             upd(b,c);
178         }
179     }
180     return 0;
181 }