2243: [SDOI2011]染色

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爱好者

Python高效编程(一)

2259
来自专栏HansBug's Lab

1297: [SCOI2009]迷路

1297: [SCOI2009]迷路 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 652  Solved:...

2865
来自专栏Golang语言社区

厚土Go学习笔记 | 30. Stringers的一个练习

让 IPAddr 类型实现 fmt.Stringer 以便用点分格式输出地址。 例如,IPAddr{1, 2, 3, 4} 应当输出 "1.2.3.4"。 这个...

37511
来自专栏十月梦想

Vue入门详解之计算属性,方法和侦听器

对于存在一个姓氏和名字,我们通过Vue计算出姓名有三种方式,计算属性,方法(methods)和侦探器三种方式!

1152
来自专栏盛国存的专栏

A Bite of GoLang(上)

A bite of GoLang(浅尝GoLang),本文只是Go语言的冰山一角,本文包含作者学习Go语言期间积累的一些小的经验,同时为了方便让读者了解到Go语...

55310
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.3节栈布局之局部变量

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

861
来自专栏容器云生态

Golang正则模块使用

最近在开发过程中会遇到一些字符串匹配相关的内容,正好去大概学习了下Golang中的regexp模块。因为目前正则模块对我来说更多的就是去匹配并处理字符串的,因此...

2495
来自专栏ACM算法日常

棋盘(数学趣味题) - HDU 5100

Consider the problem of tiling an n×n chessboard by polyomino pieces that are k×...

803
来自专栏阮一峰的网络日志

async 函数的含义和用法

本文是《深入掌握 ECMAScript 6 异步编程》系列文章的最后一篇。 Generator函数的含义与用法 Thunk函数的含义与用法 co函数库的含义...

2826
来自专栏LIN_ZONE

javascript基础重点

1.在javascript中使用 == 比较,会自动转换数据类型再比较,有时候会 得到非常诡异的结果;一般情况下使用 === 比较,它不会自动转换数据类型,如果...

902

扫码关注云+社区

领取腾讯云代金券