BZOJ1146 Network
题意
不强制在线的带修改树上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
2022年2月04日 18:54
North West Delhi JNVST Result 2022 Download Navodaya Class VI Result 2022 for NVS Mungeshpur School in North West Delhi District, Delhi with Selected list and Waiting list Candidate list in Roll number wise. Navodaya Result 2022 Delhi The following classes are available at the Jawahar Navodaya Vidyalaya Mungeshpur School (NVS): 6th, 7th, 8th, 9th, 10th, 11th, and 12th.
2023年6月27日 18:19
Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Register Your Cell Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. ekhan.net The bank has been offering a variety of handy services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Register Your Cell Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy services and amenities to its public banking clients.
2023年8月05日 17:04
BZOJ1146 Network not only represents a robust platform for technical integration but also serves describe the factors to consider when promoting effective communication in action. Its intricate architecture mirrors the key factors we must consider in promoting effective communication: clarity, active listening, cultural sensitivity, feedback, non-verbal cues, and empathy.
2023年11月20日 22:55
An intriguing journey through algorithmic complexity! The author's exploration of tree structures, DFS, and chairman tree techniques to solve the problem reflects a commendable coding endeavor, even with the humorous acknowledgment of occasional confusion. The O(Mlg^2N) algorithm adds a layer of sophistication to the intricate world of competitive programming.
2024年1月19日 21:47
Searching for reliable <a href="https://www.theresearchguardian.com/services/thesis/accounting-thesis-help/">Accounting Thesis Writing Services</a>? Look no further! These professionals excel in delivering top-notch academic content tailored to your needs. With their expertise, you can ensure a well-researched and meticulously written accounting thesis. Trust the experts for unparalleled quality and precision in your academic endeavours. #AccountingThesisWritingServices
2024年1月19日 21:49
[ليزر توريد الشفايف](https://www.drmaen.ae/ar/service/%D8%B4%D8%AF-%D8%A7%D9%84%D9%88%D8%AC%D9%87-%D8%A8%D8%AA%D9%82%D9%86%D9%8A%D8%A9-%D8%A7%D9%84%D9%85%D8%A7%D9%83%D8%B3-%D9%81%D8%A7%D9%83%D8%B3/)
[url=https://www.theresearchguardian.com/services/thesis/nursing-thesis-help/]Nursing Dissertation Writing Help[/url]