dwjshift's Blog

bzoj3221 树上询问

| Comments

原文发表时间:2014-03-25
A掉这种题之后真是一本满足>.<
如果只是在序列上做这个东西,就直接上线段树,延迟标记记录整个区间加的等差序列的首项和公差,这两个东西是可以累加的。
换成在树上路径的话,加上树链剖分就好了,在树上修改的时候注意要处理好每段链的首项和公差(在一些情况下公差是要取相反数的)。
然后要读取历史版本,所以加上持久化。不过如果在持久化的情况下直接传标记的话,空间可能会炸掉,最好还是写标记永久化。但……事实证明无需太担心空间,我写的标记永久化的只开800W就能过(但是传标记速度会很慢?P党还是小心点……)。
注意读入的那个要用long long/int64存,不然跟的类型不同,xor起来就跪了。我因为这个WA了若干次……


写了标记永久化居然能跑得这么快!

code

const
  size=10000000;
var
  n,m,i,j,qt,tot,t,a,b,totx,toty,time,rtnow:longint;
  ans,x,y:int64;
  first,father,son,dep,s,top,p,root:array[0..100000]of longint;
  v,next:array[1..200000]of longint;
  tag1,tag2,lc,rc:array[0..size]of longint;
  sum:array[0..size]of int64;
  ch:char;
  tempx,tempy:array[1..100,1..2]of longint;
 
procedure dfs(x:longint);
var
  i,max:longint;
begin
  max:=0;
  s[x]:=1;
  i:=first[x];
  repeat
    if v[i]<>father[x] then
      begin
        dep[v[i]]:=dep[x]+1;
        father[v[i]]:=x;
        dfs(v[i]);
        inc(s[x],s[v[i]]);
        if s[v[i]]>max then
          begin
            max:=s[v[i]];
            son[x]:=v[i];
          end;
      end;
    i:=next[i];
  until i=0;
end;
 
procedure dfs_(x:longint);
var
  i:longint;
begin
  inc(qt);
  p[x]:=qt;
  if s[x]=1 then
    exit;
  top[son[x]]:=top[x];
  dfs_(son[x]);
  i:=first[x];
  repeat
    if (v[i]<>father[x])and(v[i]<>son[x]) then
      begin
        top[v[i]]:=v[i];
        dfs_(v[i]);
      end;
    i:=next[i];
  until i=0;
end;
 
procedure swap;
begin
  t:=x;
  x:=y;
  y:=t;
end;
 
procedure query(now,l,r,x,y:longint);
var
  a,b:int64;
begin
  if now=0 then
    exit;
  if (l=x)and(r=y) then
    begin
      inc(ans,sum[now]);
      exit;
    end;
  a:=int64(x-l)*tag2[now]+tag1[now];
  b:=a+tag2[now]*(y-x);
  inc(ans,(a+b)*(y-x+1) shr 1);
  if y<=(l+r) shr 1 then
    query(lc[now],l,(l+r) shr 1,x,y)
  else
    if x>(l+r) shr 1 then
      query(rc[now],(l+r) shr 1+1,r,x,y)
    else
      begin
        query(lc[now],l,(l+r) shr 1,x,(l+r) shr 1);
        query(rc[now],(l+r) shr 1+1,r,(l+r) shr 1+1,y);
      end;
end;
 
procedure query;
begin
  readln(x,y);
  x:=x xor ans;
  y:=y xor ans;
  ans:=0;
  while top[x]<>top[y] do
    begin
      if dep[top[x]]<dep[top[y]] then
        swap;
      query(rtnow,1,n,p[top[x]],p[x]);
      x:=father[top[x]];
    end;
  if dep[x]>dep[y] then
    swap;
  query(rtnow,1,n,p[x],p[y]);
  writeln(ans);
end;
 
procedure modify(now,l,r,x,y,a,b:longint);
var
  t,mid:longint;
begin
  inc(tot);
  sum[tot]:=sum[now]+int64(a shl 1+b*(y-x))*(y-x+1) shr 1;
  if (l=x)and(r=y) then
    begin
      lc[tot]:=lc[now];
      rc[tot]:=rc[now];
      tag1[tot]:=tag1[now]+a;
      tag2[tot]:=tag2[now]+b;
      exit;
    end;
  t:=tot;
  tag1[t]:=tag1[now];
  tag2[t]:=tag2[now];
  mid:=(l+r) shr 1;
  if y<=mid then
    begin
      lc[t]:=tot+1;
      rc[t]:=rc[now];
      modify(lc[now],l,mid,x,y,a,b);
    end
  else
    if x>mid then
      begin
        lc[t]:=lc[now];
        rc[t]:=tot+1;
        modify(rc[now],mid+1,r,x,y,a,b);
      end
    else
      begin
        lc[t]:=tot+1;
        modify(lc[now],l,mid,x,mid,a,b);
        rc[t]:=tot+1;
        modify(rc[now],mid+1,r,mid+1,y,a+(mid-x+1)*b,b);
      end;
end;
 
procedure modify;
begin
  readln(x,y,a,b);
  x:=x xor ans;
  y:=y xor ans;
  totx:=0;
  toty:=0;
  while top[x]<>top[y] do
    if dep[top[x]]>dep[top[y]] then
      begin
        inc(totx);
        tempx[totx,1]:=p[top[x]];
        tempx[totx,2]:=p[x];
        x:=father[top[x]];
      end
    else
      begin
        inc(toty);
        tempy[toty,1]:=p[top[y]];
        tempy[toty,2]:=p[y];
        y:=father[top[y]];
      end;
  if dep[x]<dep[y] then
    begin
      inc(toty);
      tempy[toty,1]:=p[x];
      tempy[toty,2]:=p[y];
    end
  else
    begin
      inc(totx);
      tempx[totx,1]:=p[y];
      tempx[totx,2]:=p[x];
    end;
  for j:=1 to totx do
    begin
      inc(a,(tempx[j,2]-tempx[j,1]+1)*b);
      t:=tot+1;
      modify(rtnow,1,n,tempx[j,1],tempx[j,2],a-b,-b);
      rtnow:=t;
    end;
  for j:=toty downto 1 do
    begin
      t:=tot+1;
      modify(rtnow,1,n,tempy[j,1],tempy[j,2],a,b);
      rtnow:=t;
      inc(a,(tempy[j,2]-tempy[j,1]+1)*b);
    end;
  inc(time);
  root[time]:=rtnow;
end;
 
begin
  read(n,m);
  for i:=1 to n-1 do
    begin
      read(x,y);
      v[i]:=y;
      next[i]:=first[x];
      first[x]:=i;
      v[i+n]:=x;
      next[i+n]:=first[y];
      first[y]:=i+n;
    end;
  dfs(1);
  top[1]:=1;
  dfs_(1);
  readln;
  for i:=1 to m do
    begin
      read(ch);
      case ch of
        'l':
          begin
            readln(x);
            rtnow:=root[x xor ans];
          end;
        'q':
          query;
        'c':
          modify;
      end;
    end;
end.

Comments

comments powered by Disqus