首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2243: [SDOI2011]染色

2243: [SDOI2011]染色

作者头像
HansBug
发布2018-04-11 11:06:03
8350
发布2018-04-11 11:06:03
举报
文章被收录于专栏:HansBug's LabHansBug's Lab

2243: [SDOI2011]染色

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 3113  Solved: 1204

[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,表示xy之间有一条无向边。

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

“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

题解:又是一个树链剖分= =,其实越来越感觉链剖更多的是一种思想,通过树链剖分将树上的区间维护问题转化为线段树维护问题,比如这题就可以转化为一个区间覆盖与区间段数查询问题,关键在于合并区间信息

然后说些要注意的地方:1.在求出LCA再求出两条分链信息之后,记得要倒转过来,否则合并将得不到想要的(注意:区间合并具有方向性)

2.事实上,求出两条支链后不需要把交点,也就是LCA点非要排除掉(HansBug:事实上保留也根本不影响结果,想想为什么= =)

(PS:发现链剖问题每次最终坑我的都是线段树部分啊有木有TT)

  1 /**************************************************************
  2     Problem: 2243
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:14940 ms
  7     Memory:55812 kb
  8 ****************************************************************/
  9  
 10 type
 11     color=record
 12                 lef,rig,mid:longint;
 13     end;
 14     point=^node;
 15     node=record
 16                g:longint;
 17                next:point;
 18     end;
 19 var
 20    d:array[0..1000005] of color;
 21    a:array[0..100005] of point;
 22    e,len,son,num,anum,top,siz,f:array[0..1000005] of longint;
 23    c:array[0..20,0..100005] of longint;
 24    i,j,k,l,m,n,tot,root:longint;ch:char;
 25 function min(x,y:longint):longint;
 26          begin
 27               if x<y then min:=x else min:=y;
 28          end;
 29 function max(x,y:longint):longint;
 30          begin
 31               if x>y then max:=x else max:=y;
 32          end;
 33 procedure swap(var x,y:longint);
 34           var z:longint;
 35           begin
 36                z:=x;x:=y;y:=z;
 37           end;
 38 function turn(x:color):color;
 39          begin
 40               swap(x.lef,x.rig);
 41               exit(x);
 42          end;
 43 function pure(x:color):boolean;
 44          begin
 45               exit((x.lef=x.rig) and (x.mid=0));
 46          end;
 47 function number(x:color):longint;
 48          begin
 49               if x.mid>0 then exit(x.mid+2) else
 50                  if x.lef=x.rig then exit(1) else exit(2);
 51          end;
 52 function empty(x:color):boolean;
 53          begin
 54               exit((x.lef=-1) and (x.rig=-1) and (x.mid=0))
 55          end;
 56 function getcolor(x,y,z:longint):color;
 57          var p:color;
 58          begin
 59               p.lef:=x;p.rig:=y;p.mid:=z;
 60               exit(p);
 61          end;
 62 function merge(x,y:color):color;
 63          var z:color;
 64          begin
 65               if empty(x) then exit(y);
 66               if empty(y) then exit(x);
 67               z:=getcolor(x.lef,y.rig,0);
 68               if not(pure(x)) then inc(z.mid,x.mid+1);
 69               if not(pure(y)) then inc(z.mid,y.mid+1);
 70               if (z.mid>0) and (x.rig=y.lef) then dec(z.mid);
 71               exit(z);
 72          end;
 73 procedure add(x,y:longint);
 74           var p:point;
 75           begin
 76                new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
 77           end;
 78 procedure dfs(y,x:longint);
 79           var p:point;
 80           begin
 81                len[x]:=len[y]+1;
 82                c[0,x]:=y;son[x]:=0;
 83                siz[x]:=1;p:=a[x];
 84                while p<>nil do
 85                      begin
 86                           if p^.g<>y then
 87                              begin
 88                                   dfs(x,p^.g);
 89                                   if (son[x]=0) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
 90                                   inc(siz[x],siz[p^.g]);
 91                              end;
 92                           p:=p^.next;
 93                      end;
 94           end;
 95 procedure dfs2(y,x,z:longint);
 96           var p:point;
 97           begin
 98                top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
 99                if son[x]<>0 then dfs2(x,son[x],z);
100                p:=a[x];
101                while p<>nil do
102                      begin
103                           if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
104                           p:=p^.next;
105                      end;
106           end;
107 procedure built(z,x,y:longint);
108           begin
109                if x=y then
110                   d[z]:=getcolor(f[anum[x]],f[anum[x]],0)
111                else
112                    begin
113                         built(z*2,x,(x+y) div 2);
114                         built(z*2+1,(x+y) div 2+1,y);
115                         d[z]:=merge(d[z*2],d[z*2+1]);
116                    end;
117                e[z]:=-1;
118           end;
119 procedure ext(z,x,y:longint);
120           begin
121                if e[z]=-1 then exit;
122                d[z]:=getcolor(e[z],e[z],0);
123                if x<>y then
124                   begin
125                        e[z*2]:=e[z];
126                        e[z*2+1]:=e[z];
127                   end;
128                e[z]:=-1;
129           end;
130 function cover(z,x,y,l,r,t:longint):color;
131          var p1,p2:color;
132           begin
133                if l>r then if e[z]<>-1 then exit(getcolor(e[z],e[z],0)) else exit(d[z]);
134                if (l=x) and (r=y) then
135                   begin
136                        e[z]:=t;
137                        exit(getcolor(t,t,0));
138                   end;
139                ext(z,x,y);
140                p1:=cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
141                p2:=cover(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
142                d[z]:=merge(p1,p2);
143                exit(d[z]);
144           end;
145 function doit(z,x,y,l,r:longint):color;
146          var p1,p2:color;
147          begin
148               if l>r then exit(getcolor(-1,-1,0));
149               if e[z]<>-1 then exit(getcolor(e[z],e[z],0));
150               if (x=l) and (y=r) then exit(d[z]);
151               p1:=doit(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2));
152               p2:=doit(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r);
153               exit(merge(p1,p2));
154          end;
155 function getup(x,y:longint):longint;
156          var i:longint;
157          begin
158               i:=0;
159               while y>0 do
160                     begin
161                          if odd(y) then x:=c[i,x];
162                          inc(i);y:=y div 2;
163                     end;
164               exit(x);
165          end;
166 function getcom(x,y:longint):longint;
167          var i:longint;
168          begin
169               if len[x]<len[y] then swap(x,y);
170               x:=getup(x,len[x]-len[y]);
171               if x=y then exit(x);
172               for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
173                   if c[i,x]<>c[i,y] then
174                      begin
175                           x:=c[i,x];
176                           y:=c[i,y];
177                      end;
178               exit(c[0,x]);
179          end;
180 procedure treecolor(x,y,t:longint);
181           var z,i:longint;
182           begin
183                z:=getcom(x,y);
184                repeat
185                      if len[top[x]]<len[z] then i:=z else i:=top[x];
186                      cover(1,1,n,num[i],num[x],t);
187                      if i=z then break;
188                      x:=c[0,i];
189                until false;
190                repeat
191                      if len[top[y]]<len[z] then i:=z else i:=top[y];
192                      cover(1,1,n,num[i],num[y],t);
193                      if i=z then break;
194                      y:=c[0,i];
195                until false;
196           end;
197 function treecount(x,y:longint):longint;
198          var z,i:longint;p1,p2:color;
199          begin
200               p1:=getcolor(-1,-1,0);p2:=getcolor(-1,-1,0);
201               z:=getcom(x,y);
202               repeat
203                     if len[top[x]]<len[z] then i:=z else i:=top[x];
204                     p1:=merge(p1,turn(doit(1,1,n,num[i],num[x])));
205                     if i=z then break;
206                     x:=c[0,i];
207               until false;
208  
209               repeat
210                     if len[top[y]]<len[z] then i:=z else i:=top[y];
211                     p2:=merge(doit(1,1,n,num[i],num[y]),p2);
212                     if i=z then break;
213                     y:=c[0,i];
214               until false;
215  
216               exit(number(merge(p1,p2)));
217          end;
218 begin
219      readln(n,m);
220      for i:=1 to n do a[i]:=nil;
221      for i:=1 to n do read(f[i]);
222      readln;
223      for i:=1 to n-1 do
224          begin
225               readln(j,k);
226               add(j,k);add(k,j);
227          end;
228      root:=1;dfs(0,root);dfs2(0,root,root);
229      for i:=1 to trunc(round(ln(n)/ln(2)))+1 do
230          for j:=1 to n do
231              c[i,j]:=c[i-1,c[i-1,j]];
232      built(1,1,n);
233  
234      for i:=1 to m do
235          begin
236               read(ch);
237               case ch of
238                    'Q':begin
239                             readln(j,k);
240                             writeln(treecount(j,k));
241                    end;
242                    'C':begin
243                             readln(j,k,l);
244                             treecolor(j,k,l);
245                    end;
246               end;
247          end;
248      readln;
249 end.
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-05-12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2243: [SDOI2011]染色
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档