专栏首页HansBug's Lab2243: [SDOI2011]染色

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 条评论
登录 后参与评论

相关文章

  • 1191 数轴染色

    1191 数轴染色 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一条数轴...

    attack
  • openlayers2渐变色渲染

    在前文中,讲到了oL2中唯一值渲染的实现方式,在本文讲述ol2中渐变色渲染的实现方式。

    lzugis
  • 【Gym 100015B】Ball Painting(DP染色)

    There are 2N white balls on a table in two rows, making a nice 2-by-N rectangle....

    饶文津
  • OpenGL(七)- 渲染技巧:颜色混合OpenGL(七)- 渲染技巧:颜色混合

    如果这种情况出现,我们依旧是进行深度测试,丢弃蓝色部分就不合理了。现在要做的就是需要将两个颜色进行混合才为更为合理,但计算机并没有那么智能需要开发者来进行混合后...

    用户8893176
  • 染色体全局可视化

    先安装 ChromHeatMap 包,里面存放有 cytoBand坐标信息,可以简单检查一下。

    生信技能树
  • circos染色体进阶技巧

    通过指定一个染色体文件,就可以在circos中创建一个基本的圈图了。除了这种基本用法之外,还有很多的技巧。本章介绍染色体相关的进阶技巧,涉及到以下几个参数

    生信修炼手册
  • chromatin loops:染色质环简介

    利用5kb分辨率的Hi-C基因组互作图谱,科学家识别到了chromatin loop这种染色质结构,文章发表在cell上,标题如下

    生信修炼手册
  • LintCode 房屋染色题目代码

    这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用...

    desperate633
  • agc027D - Modulo Matrix(构造 黑白染色)

    构造一个$n * n$的矩阵,要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

    attack
  • css渲染(三)颜色与背景

    颜色的应用主要分为前景色、背景色和透明三个部分。 一、前景色 color   color前景色   值: <color> | inherit   初始值: 用户...

    柴小智
  • HDU 5971 Wrestling Match(二分图染色)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5971

    Ch_Zaqdt
  • cf19E. Fairy(奇环 二分图染色)

    非常有思维含量的一道题,队爷的论文里介绍了一种\(N \sqrt{N}\)的暴力然鹅看不懂。。

    attack
  • chromosome-territories:染色质疆域简介

    人类基因组大小在3G左右,这么多的DNA线性排列,完全展开其长度可以达到2米,而细胞直径是微米级别的,这意味着DNA在细胞核内肯定是高度折叠的。众所周知,结构决...

    生信修炼手册
  • A/B compartment:染色质区室简介

    Hi-C技术的出现推动了三维基因组学的发展,利用Hi-C技术,科学家不仅证实了染色质疆域的存在,而且进一步发现了更多染色质的三维特征。

    生信修炼手册
  • 扇形染色问题 Python解法

    将一个圆形等分成N个小扇形,将这些扇形标记为1,2,3,…,N。现在使用M种颜色对每个扇形进行涂色,每个扇形涂一种颜色,且相邻的扇形颜色不同。

    大鹅
  • LeetCode 785. 判断二分图(染色法)

    如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。

    Michael阿明
  • 基础渲染系列(二)——着色器

    这是渲染系列的第二篇文章,第一篇讲述的是矩阵,这次我们会写我们的第一个Shader并且导入一张纹理。

    放牛的星星
  • X染色体的基因型填充

    在所有的基因型填充软件中,都会区分常染色体和X染色体,分别进行填充,为何对于X染色体要单独处理呢?

    生信修炼手册
  • LCP 34. 二叉树染色(树形dp)

    glm233

扫码关注云+社区

领取腾讯云代金券