THUSC Day 0 训练日记

今天乘火车参加THUSC.
在火车上捉了WC2010 重建计划，大概是给定一棵树，求一条长度在[L,R]之间的简单路径使得平均值最大。
解法显然二分答案然后树分治各种乱搞…… 各种乱搞的话最显而易见的是直接线段树。但这样是O(Nlg^3N)的，跑最大的点要近1分钟…… 于是NB的事情就发生了，考虑每个子树的最深深度，然后按最深深度给子树排序。子树内部再按每个结点的深度排序。然后对每棵子树的查询都可以单调队列，做 到O(D+maxD)，D是当前子树的深度，maxD是前面最深的子树的深度。然后因为我们已经按最深深度对所有子树排序了，所以maxD<=D， 也就是时间复杂度O(D)，也就是总复杂度O(sigma(D))，即子树大小。这样处理的过程就少了一个log。但问题来了，我们这个处理要排序后才能 进行，这样排序复杂度就有一个log了，这时NB的事情再次发生，我们可以在树分治内部进行二分！对于某个结点树分治的内容已经确定了，可以排序后二分判 定时直接用这个排序后的结果，然后排序的log就不是在二分的log里面了！ 这样就彻底偷掉一个log，变成O(Nlg^2N)，就可以过了。

code

const eps=1e-9;
var
b:array[0..300010] of record id,wg,next,anti:longint; ok:boolean; end;
tail:array[0..100010] of longint;
ep:longint;
 
function Create(x,y:longint):longint;
begin inc(ep);
      with b[ep] do
      begin id:=x; wg:=y;
            ok:=true; next:=-1;
      end;
      exit(ep);
end;
 
procedure add(x,y,z:longint);
begin b[tail[x]].next:=Create(y,z);
      tail[x]:=ep;
end;
 
var
gp,gpi:longint;
sz:array[0..100010] of longint;
 
procedure dfs1(cur,pre:longint);
var now:longint;
begin now:=cur; sz[cur]:=1;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if (not b[now].ok)or(b[now].id=pre) then continue;
            dfs1(b[now].id,cur); inc(sz[cur],sz[b[now].id]);
      end;
end;
 
procedure dfs2(root,cur,pre:longint);
var now,max:longint;
begin now:=cur; max:=sz[root]-sz[cur];
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if (not b[now].ok)or(b[now].id=pre) then continue;
            if sz[b[now].id]>max then max:=sz[b[now].id];
            dfs2(root,b[now].id,cur);
      end;
      if max<gp then begin gp:=max; gpi:=cur; end;
end;
 
function gravity(root:longint):longint;
begin dfs1(root,root);
      gp:=1000000; gpi:=0;
      dfs2(root,root,root);
      exit(gpi);
end;
 
type
      atype=record depth:longint; weight:extended; belong,maxdep:longint; end;
 
var
all:longint;
d:array[0..100010] of atype;
 
procedure dfs3(cur,pre,dep:longint; wg:extended; bel:longint);
var now:longint;
begin inc(all); d[all].depth:=dep; d[all].weight:=wg; d[all].belong:=bel;
      now:=cur;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if (not b[now].ok)or(b[now].id=pre) then continue;
            dfs3(b[now].id,cur,dep+1,wg+b[now].wg,bel);
      end;
end;
 
var
final:extended;
LL,UU:longint;
dt:array[0..100010] of extended;
q:array[0..100010] of record where:longint; dt:extended; end;
 
function ok(root:longint; mid:extended):boolean;
var last,cur,_l,_r,i,head,tail,kt:longint;
begin for i:=1 to all do if (LL<=d[i].depth)and(d[i].depth<=UU)and(d[i].weight-d[i].depth*mid>-eps) then exit(true);
      for i:=1 to d[all].maxdep do dt[i]:=-1e50;
      last:=1; cur:=2;
      while (cur<=all)and(d[cur].belong=d[last].belong) do inc(cur);
      while cur<=all do
      begin for i:=last to cur-1 do 
                  if d[i].depth<=UU then 
                        if d[i].weight-mid*d[i].depth>dt[d[i].depth] then
                              dt[d[i].depth]:=d[i].weight-mid*d[i].depth;
            head:=1; tail:=0; kt:=0;
            last:=cur;
            while (cur<=all)and(d[cur].belong=d[last].belong) do
            begin _l:=LL-d[cur].depth; _r:=UU-d[cur].depth;
                  if _l<1 then _l:=1; if _r>d[last].maxdep then _r:=d[last].maxdep;
                  if _l<=_r then
                  begin while (kt<_r) do
                        begin inc(kt);
                              while (head<=tail)and(dt[kt]>q[tail].dt) do dec(tail);
                              inc(tail); q[tail].dt:=dt[kt]; q[tail].where:=kt;
                        end;
                        while (head<=tail)and(q[head].where<_l) do inc(head);
                        if q[head].dt+d[cur].weight-d[cur].depth*mid>-eps then
                              exit(true);
                  end;
                  inc(cur);
            end;
      end;
      exit(false);
end;
 
var ccc:longint;
 
function cmp(const a,b:atype):boolean;
begin if a.maxdep<>b.maxdep then exit(a.maxdep<b.maxdep);
      if a.belong<>b.belong then exit(a.belong<b.belong);
      exit(a.depth>b.depth);
end;
 
procedure sort(l,r:longint);
var i,j:longint;
    x,y:atype;
begin i:=l;
      j:=r;
      x:=d[l+random(r-l+1)];
      repeat
            while cmp(d[i],x) do inc(i);
            while cmp(x,d[j]) do dec(j);
            if not(i>j) then
            begin y:=d[i]; d[i]:=d[j]; d[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
procedure Decompose(_r:longint);
var now,root,i,cur,last,max:longint; left,right,mid:extended;
begin root:=gravity(_r);
      all:=0;
      now:=root;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if not b[now].ok then continue;
            dfs3(b[now].id,root,1,b[now].wg,b[now].id);
      end;
      cur:=1;
      while cur<=all do
      begin last:=cur; max:=0;
            while (cur<=all)and(d[last].belong=d[cur].belong) do
            begin if d[cur].depth>max then max:=d[cur].depth;
                  inc(cur);
            end;
            for i:=last to cur-1 do d[i].maxdep:=max;
      end;
      sort(1,all);
      if all=0 then exit;
      left:=0; right:=1000001;
      while left+5e-5<=right do
      begin mid:=(left+right)/2;
            if ok(root,mid) then left:=mid else right:=mid;
      end;
      if left>final then final:=left;
      now:=root;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if not b[now].ok then continue;
            b[now].ok:=false; b[b[now].anti].ok:=false;
            Decompose(b[now].id);
      end;
end;
 
procedure lemon();
var i,x,y,z,n:longint;
begin readln(n); ep:=0;
      for i:=1 to n do tail[i]:=Create(i,0);
      readln(LL,UU);
      for i:=1 to n-1 do
      begin readln(x,y,z);
            add(x,y,z); b[ep].anti:=ep+1;
            add(y,x,z); b[ep].anti:=ep-1;
      end;
      final:=0;
      Decompose(1);
      writeln(final:0:3);
end;
 
begin
lemon();
end.

在宾馆又捉了一题，国家集训队2012互测题，李超的attack. 这题大概是平面上给n个点有权值，然后要求支持交换两个点的权值、查询一个矩形内的点的k大权值。
做法也是比较乱搞的。首先按x轴排序，分成n^0.5块。然后每一块内按y坐标排序。于是每个询问如果x区间完整覆盖了一个块，那么块内符合条件的点必然 是连续一段。然后问题就变成经典的区间k大带修改的问题了。这个可以用主席树或划分树，然后二分答案。但有个更好的做法就是直接用函数式trie树。这样 树的形态是相同的，就不用二分答案了，修改也方便。但因为修改时候会暴力重建两个块的函数式数据结构，所以直接函数式会爆内存。一个处理方法就是，使用静 态数组，然后如果数组快要爆了就直接重建整个函数式数据结构。这样就能过了。时间复杂度是O(32*(N+Q)*N^0.5).

code

type
      atype=record
                  x,y,w,where:longint;
            end;
var
d:array[0..100010] of atype;
b:array[0..40000000] of record
                              ch:array[false..true] of longint;
                              sz:longint;
                        end;
ep:longint;
bg,ed,root,bgx,edx,citywhere:array[0..100010] of longint;
w:array[0..100010] of record node,wg:longint; end;
all:longint;
 
procedure sort(l,r:longint);
var i,j:longint;
    x,y:atype;
begin i:=l;
      j:=r;
      x:=d[l+random(r-l+1)];
      repeat
            while d[i].x<x.x do inc(i);
            while x.x<d[j].x do dec(j);
            if not(i>j) then
            begin y:=d[i]; d[i]:=d[j]; d[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
procedure sort2(l,r:longint);
var i,j:longint;
    x,y:atype;
begin i:=l;
      j:=r;
      x:=d[l+random(r-l+1)];
      repeat
            while d[i].y<x.y do inc(i);
            while x.y<d[j].y do dec(j);
            if not(i>j) then
            begin y:=d[i]; d[i]:=d[j]; d[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort2(l,j);
      if i<r then sort2(i,r);
end;
 
function create(_s:longint):longint;
begin inc(ep); 
      b[ep].sz:=_s;
      fillchar(b[ep].ch,sizeof(b[ep].ch),0);
      exit(ep);
end;
 
function serere(root,dt,dep:longint):longint;
begin inc(ep); serere:=ep; b[serere]:=b[root]; inc(b[serere].sz);
      if dep<0 then exit;
      b[serere].ch[dt and (1<<dep)>0]:=serere(b[serere].ch[dt and (1<<dep)>0],dt,dep-1);
end;
 
function query(kth,dep:longint):longint;
var count,i:longint;
begin if dep<0 then exit(0);
      count:=0;
      for i:=1 to all do inc(count,b[b[w[i].node].ch[false]].sz*w[i].wg);
      //writeln(kth,' ',count);
      if count>=kth then
      begin for i:=1 to all do w[i].node:=b[w[i].node].ch[false];
            exit(query(kth,dep-1));
       end
      else begin
            for i:=1 to all do w[i].node:=b[w[i].node].ch[true];
            exit(query(kth-count,dep-1)+1<<dep);
      end;
end;
 
procedure lemon();
var n,i,bsz,csz,cur,j,_Q,_cq,x1,y1,x2,y2,kth,x,y,temp,left,right,mid,ll,rr,final,_ep:longint;
    ch,ch2:char;
begin readln(n,_Q);
      for i:=1 to n do begin readln(d[i].x,d[i].y,d[i].w); d[i].where:=i; end;
      sort(1,n);
      ep:=0; root[0]:=create(0);
      bsz:=trunc(sqrt(n)); csz:=0; cur:=1;
      while cur<=n do
      begin inc(csz); bg[csz]:=cur; ed[csz]:=cur+bsz-1; if ed[csz]>n then ed[csz]:=n;
            bgx[csz]:=d[bg[csz]].x; edx[csz]:=d[ed[csz]].x; cur:=ed[csz]+1;
      end;
      for i:=1 to csz do
      begin sort2(bg[i],ed[i]);
            root[bg[i]]:=serere(root[0],d[bg[i]].w,30);
            for j:=bg[i]+1 to ed[i] do root[j]:=serere(root[j-1],d[j].w,30);
      end;
      for i:=1 to n do citywhere[d[i].where]:=i;
      for _cq:=1 to _Q do
      begin _ep:=ep;
            repeat read(ch); until ch in ['Q','S'];
            repeat read(ch2); until ch2=' ';
            if ch='Q' then 
            begin readln(x1,y1,x2,y2,kth); all:=0;
                  if x1>x2 then begin temp:=x1; x1:=x2; x2:=temp; end;
                  if y1>y2 then begin temp:=y1; y1:=y2; y2:=temp; end;
                  for i:=1 to csz do
                        if (x1<=bgx[i])and(edx[i]<=x2) then
                        begin if (d[bg[i]].y>y2)or(d[ed[i]].y<y1) then continue;
                              left:=bg[i]; right:=ed[i];
                              while left<>right do
                              begin mid:=(left+right+1)>>1;
                                    if d[mid].y>y2 then right:=mid-1 else left:=mid;
                              end;
                              rr:=left;
                              left:=bg[i]; right:=ed[i];
                              while left<>right do
                              begin mid:=(left+right)>>1;
                                    if d[mid].y>=y1 then right:=mid else left:=mid+1;
                              end;
                              ll:=left;
                              if ll<>bg[i] then begin inc(all); w[all].node:=root[ll-1]; w[all].wg:=-1; end;
                              inc(all); w[all].node:=root[rr]; w[all].wg:=1;
                         end
                        else  if ((bgx[i]<=x1)and(x1<=edx[i]))or((bgx[i]<=x2)and(x2<=edx[i])) then
                              begin inc(all); w[all].node:=create(0); w[all].wg:=1;
                                    for j:=bg[i] to ed[i] do
                                          if (x1<=d[j].x)and(d[j].x<=x2)and(y1<=d[j].y)and(d[j].y<=y2) then
                                                w[all].node:=serere(w[all].node,d[j].w,30);
 
                                    if b[w[all].node].sz=0 then dec(all);
                              end;
                  final:=query(kth,30);
                  if final=maxlongint then writeln('It doesn',chr(39),'t exist.') else writeln(final);
                  ep:=_ep;
             end
            else begin
                  readln(x,y); x:=citywhere[x+1]; y:=citywhere[y+1];
                  temp:=d[x].w; d[x].w:=d[y].w; d[y].w:=temp;
                  for i:=1 to csz do
                        if (bg[i]<=x)and(x<=ed[i]) then
                        begin root[bg[i]]:=serere(root[0],d[bg[i]].w,30);
                              for j:=bg[i]+1 to ed[i] do root[j]:=serere(root[j-1],d[j].w,30);
                         end
                        else  if (bg[i]<=y)and(y<=ed[i]) then
                              begin root[bg[i]]:=serere(root[0],d[bg[i]].w,30);
                                    for j:=bg[i]+1 to ed[i] do root[j]:=serere(root[j-1],d[j].w,30);
                              end;
            end;
            if ep>38000000 then
            begin ep:=0; root[0]:=Create(0);
                  for i:=1 to csz do
                  begin root[bg[i]]:=serere(root[0],d[bg[i]].w,30);
                        for j:=bg[i]+1 to ed[i] do root[j]:=serere(root[j-1],d[j].w,30);
                  end;
            end;
      end;
end;
 
begin
lemon();
end.