BZOJ 2243：染色（树链剖分+区间合并线段树）

[SDOI2011]染色
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]之间。

分析：

树链剖分后用线段树维护数据，还是比较好的一道题。

树链剖分的第一个dfs要求出各个点的深度d，父节点fa，子树节点数sz，重儿子son，第二个dfs求出每个点在序列中的位置id，所在路径顶端节点编号top。

第二个dfs就是用来剖分路径的，要注意必须先对重儿子处理，只有这样一条路径的点在序列上才是连续的，这样才能用线段树维护。

然后就是线段树维护了，不要忘记修改x到y的权值要用id[x]和id[y]表示，另外注意任何对线段树的操作必须先下传懒惰标记。

在查询时由于要跨过多条路径，相邻两个路径相接的地方颜色相同的情况也要判断。

代码：

program putcolor;

type

  thing=record

     l,r,v,s,e:longint;

  end;

  point=^node;

    node=record

     x:longint; next:point;

  end;

var

  a:array[..]of point;

  dat:array[..]of thing;

  sz,son,id,fa,v,b,d,top:array[..]of longint;

  n,i,m,len:longint;

procedure add(x,y:longint);

var p:point;

begin

  new(p); p^.x:=y; p^.next:=a[x]; a[x]:=p;

end;

procedure swap(var x,y:longint);

var t:longint;

begin

  t:=x; x:=y; y:=t;

end;

procedure dfs1(x:longint);

var y:longint; p:point;

begin

  new(p); p:=a[x]; sz[x]:=;

  while p<>nil do

   begin

     if p^.x=fa[x] then begin p:=p^.next; continue; end;

     y:=p^.x; fa[y]:=x; d[y]:=d[x]+;

     dfs1(y);

     inc(sz[x],sz[y]); if sz[y]>sz[son[x]] then son[x]:=y;

     p:=p^.next;

   end;

end;

procedure dfs2(x,k:longint);

var i:longint; p:point;

begin

  inc(len); id[x]:=len; b[len]:=v[x]; top[x]:=k;

  if son[x]> then dfs2(son[x],k);

  new(p); p:=a[x];

  while p<>nil do

   begin

     if (p^.x<>fa[x])and(p^.x<>son[x]) then dfs2(p^.x,p^.x);

     p:=p^.next;

   end;

end;

procedure down(p,x,y:longint);

var l,r,v:longint;

begin

  if x=y then exit;

  l:=p*; r:=p*+; v:=dat[p].e;

  dat[l].l:=v; dat[l].r:=v; dat[l].s:=;dat[l].e:=v;

  dat[r].l:=v; dat[r].r:=v; dat[r].s:=;dat[r].e:=v;

  dat[p].e:=-;

end;

procedure update(p,x,y:longint);

var l,r:longint;

begin

  if x=y then exit;

  l:=p*; r:=p*+;

  dat[p].l:=dat[l].l; dat[p].r:=dat[r].r;

  dat[p].s:=dat[l].s+dat[r].s;

  if dat[l].r=dat[r].l then dec(dat[p].s);

end;

procedure build(p,l,r:longint);

var mid:longint;

begin

  dat[p].s:=;  dat[p].e:=-;

  if l=r then exit;

  mid:=(l+r) div ;

  build(p*,l,mid); build(p*+,mid+,r);

end;

procedure change(x,y,p,l,r,v:longint);

var mid:longint;

begin

  if dat[p].e>= then down(p,l,r);

  if (x<=l)and(r<=y) then

  begin dat[p].l:=v; dat[p].r:=v; dat[p].s:=; dat[p].e:=v; end else

  begin

    mid:=(l+r) div ;

    if x<=mid then  change(x,y,p*,l,mid,v);

    if y>mid  then  change(x,y,p*+,mid+,r,v);

    update(p,l,r);

  end;

end;

function query(x,y,p,l,r:longint):longint;

var mid,ans:longint;

begin

  if (x<=l)and(r<=y) then exit(dat[p].s)

  else

   begin

    mid:=(l+r) div ;if dat[p].e>= then down(p,l,r);  ans:=;

    if x<=mid then ans:=query(x,y,p*,l,mid);

    if y>mid  then inc(ans,query(x,y,p*+,mid+,r));

    if (x<=mid)and(y>mid) then

     if dat[p*].r=dat[p*+].l then dec(ans);

    exit(ans);

   end;

end;

function get(p,l,r,x:longint):longint;

var mid:longint;

begin

  if dat[p].e>= then down(p,l,r);

  if l=x then exit(dat[p].l);

  mid:=(l+r) div ;

  if x<=mid then exit(get(p*,l,mid,x));

  if x>mid then exit(get(p*+,mid+,r,x));

end;

procedure solvechange(x,y,z:longint);

var fx,fy,t,ans:longint;

begin

  fx:=top[x]; fy:=top[y]; ans:=;

  while fx<>fy do

   begin

     if d[fx]<d[fy] then begin  swap(x,y);  swap(fx,fy);; end;

     change(id[fx],id[x],,,n,z);

     x:=fa[fx]; fx:=top[x];

   end;

  if d[x]>d[y] then swap(x,y);

  change(id[x],id[y],,,n,z);

end;

function solvequery(x,y:longint):longint;

var fx,fy,t,ans:longint;

begin

  fx:=top[x]; fy:=top[y]; ans:=;

  while fx<>fy do

   begin

     if d[fx]<d[fy] then begin  swap(x,y); swap(fx,fy); end;

     inc(ans,query(id[fx],id[x],,,n));

     if get(,,n,id[fx])=get(,,n,id[fa[fx]]) then dec(ans);

     x:=fa[fx]; fx:=top[x];

   end;

  if d[x]>d[y] then swap(x,y);

  inc(ans,query(id[x],id[y],,,n));

  exit(ans);

end;

procedure solve;

var i,x,y,z:longint;  c:char;

begin

  build(,,n);

  for i:= to n do change(id[i],id[i],,,n,v[i]);

  for i:= to m do

   begin

     read(c);

     if c='C' then begin read(x,y,z);  solvechange(x,y,z); end

      else begin read(x,y); writeln(solvequery(x,y)); end;

     readln;

   end;

end;

procedure int;

var i,x,y:longint; p:point;

begin

  readln(n,m);

  for i:= to n do read(v[i]);

  for i:= to n- do

   begin

     readln(x,y);

     add(x,y); add(y,x);

   end;

end;

begin

  int;

  dfs1();dfs2(,);

  solve;

end.

巴特西

BZOJ 2243：染色（树链剖分+区间合并线段树）

最新文章

热门文章