BZOJ1146 Network - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ1014 Prefix
BZOJ1042 Coins

BZOJ1146 Network

Hoblovski posted @ 2014年6月26日 00:38 in Solutions with tags bzoj DFS序 主席树 树链剖分 树套树 , 987 阅读
题意
        不强制在线的带修改树上k大
        N,M!>80000
 
Tag 树链剖分 DFS序 主席树 树状数组 线段树套平衡树
 
代码好题.第一次树套树套树4小时1A,这次DFS序主席树乱搞一共5小时1A.
先来最直观的解法
        树链剖分+线段树套平衡树,第一眼的算法.
        二分答案再用树链剖分计数,比区间k大多的就是个树链剖分.
        时间复杂度        O(Mlg^4N)
Applepi神牛给出了一个O(Mlg^3N)的解法,可惜我没有看懂
Applepi神牛给出了一个O(Mlg^2N)的解法,可惜我还是没有看懂
以下是本蒟蒻的O(Mlg^2N)的算法,虽然自己用这个算法A了还是语死早不能描述清楚
先搞出DFS序和LCA预处理(我只会树链剖分做LCA),建立一个权值线段树的数组
每个元素w对其管辖的子树在DFS序中的区间[L,R]有贡献{[L,R],w,+1}
区间不好搞于是我们把这个元素拆成2个{L,w,+1},{R+1,w,-1} 特判一下R=N
于是某前缀和就代表了对应结点到根的路径上的权值分布情况,这是初始没修改的情况
然后把所有L,R+1排序时候按主席树的搞法来搞
修改就另开一个树状数组套权值线段树按上面的思想类似的维护
这样我们就可以比较容易得到某结点到根的路径上的权值分布情况
下面的"权值线段树"就指"某结点到根的路径上的权值分布情况"了.
之后询问u,v就权值线段树作差
        u的权值线段树 + v的权值线段树 - 2*fa[lca(u,v)]的权值线段树
特判一下lca(u,v),按主席树的方法带修改区间k大什么什么什么的就可以了
以下是一些废话
其实我自己也不清楚是怎么A的www反正就是乱搞啦,虽然最后还是Pascal Rank1.
好像我很怨念"什么什么k大"的,BZOJ上1901区间k大蒟蒻是Pascal Rank1(暂定),1146树上k大也是Pascal Rank1(暂定)
看哪天来个仙人掌k大(笑)
感觉这道题整体二分也能搞的样子,试一试?
 
树链剖分套线段树套平衡树
program bzoj1146;
 
type tedge=record
        n,next:longint;
     end;
     pnode=^tnode;
     tnode=record
        v,p,w,size:longint;
        l,r:pnode;
     end;
     snode=record
        n,t1:longint;
     end;
 
const maxn=80017;
      maxint=longint($3f3f3f3f);
      minint=longint($c0c0c0c0);
      maxans=longint(100000000);
 
var g,size,son,fa,dep,top,pos,initw,inits:array[0..maxn] of longint;
    node:array[0..maxn*5] of pnode;
    v:array[0..maxn] of boolean;
    mem:array[0..maxn*2] of tedge;
    s:array[1..maxn] of snode;
    n,m,memsize,segsize,rer:longint;
    null:pnode;
 
function min(i,j:longint):longint; begin
if i<j then exit(i) else exit(j);  end;
 
function max(i,j:longint):longint; begin
if i>j then exit(i) else exit(j);  end;
 
procedure treap_init;
begin
new(null); randomize;
with null^ do begin
        v:=0; p:=maxint; w:=0; size:=0; l:=null; r:=null;
end;
end;
 
procedure lrot(var i:pnode);
var j:pnode;
begin
j:=i^.r; i^.r:=j^.l; j^.l:=i; j^.size:=i^.size;
i^.size:=i^.l^.size+i^.r^.size+i^.w; i:=j;
end;
 
procedure rrot(var i:pnode);
var j:pnode;
begin
j:=i^.l; i^.l:=j^.r; j^.r:=i; j^.size:=i^.size;
i^.size:=i^.l^.size+i^.r^.size+i^.w; i:=j;
end;
 
procedure insert(var i:pnode;j:longint);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); w:=1; size:=1; l:=null; r:=null;
        end;
end else if j<i^.v then begin
        insert(i^.l,j); inc(i^.size); if i^.l^.p<i^.p then rrot(i);
end else if j>i^.v then begin
        insert(i^.r,j); inc(i^.size); if i^.r^.p<i^.p then lrot(i);
end else begin
        inc(i^.w); inc(i^.size);
end;
end;
 
procedure delete(var i:pnode;j:longint);
begin
if j=i^.v then
        if i^.w>1 then begin
                dec(i^.size); dec(i^.w);
        end else if i^.l=null then i:=i^.r
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); dec(i^.size); delete(i^.r,j);
        end else begin
                lrot(i); dec(i^.size); delete(i^.l,j);
        end
else if j<i^.v then begin
        delete(i^.l,j); dec(i^.size);
end else begin
        delete(i^.r,j); dec(i^.size);
end;
end;
 
function rank(i:pnode;j:longint):longint;
begin
rank:=0;
while (i<>null) do
        if j=i^.v then exit(rank+i^.l^.size)
        else if j<i^.v then i:=i^.l else begin
                inc(rank,i^.l^.size+i^.w); i:=i^.r;
        end;
end;
 
function succ(i:pnode;j:longint):longint;
                                                (* INCLUSIVE *)
begin
if i=null then exit(maxint);
if i^.v<j then exit(succ(i^.r,j));
succ:=succ(i^.l,j); if succ=maxint then succ:=i^.v;
end;
 
procedure build(i,l,r:longint);
var mid:longint;
begin
node[i]:=null;
for mid:=l to r do insert(node[i],inits[mid]);
if l<r then begin
        mid:=(l+r)>>1;
        build(i<<1,l,mid); build(i<<1+1,mid+1,r);
end;
end;
 
function intrank(i,l,r,  il,ir,j:longint):longint;
var mid:longint;
begin
if (l=il)and(r=ir) then exit(rank(node[i],j));
mid:=(l+r)>>1; intrank:=0;
if il<=mid then intrank:=intrank(i<<1,l,mid,  il,min(mid,ir),j);
if ir>mid then inc(intrank,intrank(i<<1+1,mid+1,r,  max(mid+1,il),ir,j ));
end;
 
function intsucc(i,l,r,  il,ir,j:longint):longint;
var mid:longint;
begin
if (l=il)and(r=ir) then exit(succ(node[i],j));
mid:=(l+r)>>1; intsucc:=maxint;
if il<=mid then intsucc:=intsucc(i<<1,l,mid,  il,min(mid,ir),j);
if ir>mid then intsucc:=min(intsucc,intsucc(i<<1+1,mid+1,r,  max(mid+1,il),ir,j));
end;
 
procedure intedit(i,l,r,  j,k:longint);
var mid:longint;
begin
while l<>r do begin
        delete(node[i],inits[j]); insert(node[i],k);
        mid:=(l+r)>>1; if j<=mid then begin
                i:=i<<1; r:=mid;
        end else begin
                i:=i<<1+1; l:=mid+1;
        end;
end; delete(node[i],inits[j]); insert(node[i],k); inits[j]:=k;
end;
 
procedure insnbs(u,v:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; next:=g[v];
end; g[v]:=memsize;
end;
 
procedure dfs1(u:longint);
var head:longint;
begin
fillchar(v,sizeof(v),0); dep[u]:=1; fa[u]:=0;
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin
        head:=s[rer].n;
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do
                s[rer].t1:=mem[s[rer].t1].next;
        if s[rer].t1=0 then begin
                inc(size[head]);                inc(size[fa[head]],size[head]);
                if (son[fa[head]]=0)or(size[head]>size[son[fa[head]]]) then
                        son[fa[head]]:=head;
                dec(rer);
        end else begin
                inc(rer);                       s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];         v[s[rer].n]:=true;
                dep[s[rer].n]:=dep[head]+1;     fa[s[rer].n]:=head;
        end;
end;
end;
 
procedure dfs2(u:longint);
var i:longint;
begin
fillchar(v,sizeof(v),0); top[u]:=u;
segsize:=1; pos[u]:=segsize; inits[segsize]:=initw[u];
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do
                s[rer].t1:=mem[s[rer].t1].next;
        if (son[s[rer].n]<>0)and(not v[son[s[rer].n]]) then begin
                inc(rer);                       s[rer].n:=son[s[rer-1].n];
                s[rer].t1:=g[s[rer].n];         v[s[rer].n]:=true;
                top[s[rer].n]:=top[s[rer-1].n]; inc(segsize);
                pos[s[rer].n]:=segsize;         inits[segsize]:=initw[s[rer].n];
        end else if s[rer].t1=0 then dec(rer) else begin
                inc(rer);                       s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];         v[s[rer].n]:=true;
                top[s[rer].n]:=s[rer].n;        inc(segsize);
                pos[s[rer].n]:=segsize;         inits[segsize]:=initw[s[rer].n];
        end;
end;
end;
 
function pthrank(i,j,  k:longint):longint;
                                                        (* CNT( on [i<->j] ;; point ;; point weight LESS than k *)
begin
pthrank:=0;
while top[i]<>top[j] do
        if dep[top[i]]>dep[top[j]] then begin
                inc(pthrank, intrank(1,1,n,  pos[top[i]],pos[i],k ));
                i:=fa[top[i]];
        end else begin
                inc(pthrank, intrank(1,1,n,  pos[top[j]],pos[j],k ));
                j:=fa[top[j]];
        end;
if dep[i]<dep[j] then inc(pthrank,intrank(1,1,n,  pos[i],pos[j],k ))
                 else inc(pthrank,intrank(1,1,n,  pos[j],pos[i],k ));
end;
 
function pthsucc(i,j,  k:longint):longint;
begin
pthsucc:=maxint;
while top[i]<>top[j] do
        if dep[top[i]]>dep[top[j]] then begin
                pthsucc:=min(pthsucc,intsucc(1,1,n,  pos[top[i]],pos[i],k));
                i:=fa[top[i]];
        end else begin
                pthsucc:=min(pthsucc,intsucc(1,1,n,  pos[top[j]],pos[j],k));
                j:=fa[top[j]];
        end;
if dep[i]<dep[j] then pthsucc:=min(pthsucc,intsucc(1,1,n,  pos[i],pos[j],k))
                 else pthsucc:=min(pthsucc,intsucc(1,1,n,  pos[j],pos[i],k));
 
end;
 
function pthselect(i,j,  k:longint):longint;
                                                        (* find point weight ;; point on [i<->j] ;; k pwoij LESS than *)
var l,r,mid:longint;
begin
l:=0; r:=maxans; mid:=pthrank(i,j,  maxans);
if mid<=k then exit(-1);
while l<>r do begin
        mid:=(l+r)>>1;
        if pthrank(i,j,  mid+1)<=k then l:=mid+1 else r:=mid;
end; exit(pthsucc(i,j,  l));
end;
 
function pthrevselect(i,j,  k:longint):longint;
var l,r,mid:longint;
begin
l:=0; r:=maxans; mid:=pthrank(i,j,  maxans);
if mid<=k then exit(-1) else k:=mid-k-1;
while l<>r do begin
        mid:=(l+r)>>1;
        if pthrank(i,j,  mid+1)<=k then l:=mid+1 else r:=mid;
end; exit(pthsucc(i,j,  l));
end;
 
procedure init;
var i,j,k,u,v:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,m); for i:=1 to n do read(initw[i]); readln;
for i:=1 to n-1 do begin
        readln(u,v); insnbs(u,v);
end;
end;
 
procedure work;
const errmsg='invalid request!';
var i,j,k:longint;
begin
while m>0 do begin dec(m);
        readln(k,i,j);
        if k=0 then begin
                intedit(1,1,n,  pos[i],j);
        end else begin
                k:=pthrevselect(i,j,k-1);
                if k=-1 then writeln(errmsg) else writeln(k);
        end;
end;
end;
 
begin
treap_init;
init;
dfs1(1);
dfs2(1);
build(1,1,n);
work;
end.

DFS序套主席树

算了介于是Pasal Rank 1暂定,就不发代码了233


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter