【Tyvj2133&BZOJ1146】网络管理Network（树套树，DFS序，树状数组，主席树，树上差分）
2024-09-29 21:33:41
题意：有一棵N个点的树，每个点有一个点权a[i]，要求在线实现以下操作：
1：将X号点的点权修改为Y
2：查询X到Y的路径上第K大的点权
n,q<=80000 a[i]<=10^8
思路：此题明显地体现了我对主席树理解不深
树上路径K大可以直接用树剖+二分答案+树做
但DFS序+主席树也可以
对于点U，它能影响DFS序上的区间(st[u],ed[u])
所以维护方法就是类似序列K大一样 s[st[u]]++ s[ed[u]+1]--
对于路径(x,y)，信息为s[x]+s[y]-s[lca(x,y)]-s[fa[lca(x,y)]]
但因为是在树上的操作，所以每个点是从它在树上的父亲继承下来的，并不是DFS序上的前一个继承的
所以在DFS时就可以建立一棵没有修改过的原树
对于询问，再建立一棵树只做更改，询问时加上原树的信息即可
不开两棵树可以，不过需要主席树合并
var t:array[..]of record
l,r,s:longint;
end;
f:array[..,..]of longint;
head,vet,next,st,ed,dep,flag,hash,root1,root2,b:array[..]of longint;
d:array[..,..]of longint;
a:array[..]of longint;
q1,q2:array[..]of longint;
n,m,i,j,tot,time,up,la,lb,cnt,q,x,y,tmp,p,sum,z,f1,f2,f3,f4:longint; procedure add(a,b:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
head[a]:=tot;
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; function find(x:longint):longint;
var l,r,mid:longint;
begin
l:=; r:=up;
while l<=r do
begin
mid:=(l+r)>>;
if hash[mid]=x then exit(mid);
if hash[mid]<x then l:=mid+
else r:=mid-;
end;
end; procedure update(l,r:longint;var p:longint;v,x:longint);
var mid:longint;
begin
inc(cnt); t[cnt]:=t[p];
p:=cnt; t[p].s:=t[p].s+x;
if l=r then exit;
mid:=(l+r)>>;
if v<=mid then update(l,mid,t[p].l,v,x)
else update(mid+,r,t[p].r,v,x);
end; procedure dfs(u:longint);
var e,v,i,tmp:longint;
begin
for i:= to do
begin
if dep[u]<(<<i) then break;
f[u,i]:=f[f[u,i-],i-];
end;
tmp:=find(a[u]);
root1[u]:=root1[f[u,]];
update(,up,root1[u],tmp,);
inc(time); st[u]:=time; ed[u]:=time;
flag[u]:=;
e:=head[u];
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
f[v,]:=u;
dep[v]:=dep[u]+;
dfs(v);
ed[u]:=max(ed[u],ed[v]);
end;
e:=next[e];
end;
end; function lca(x,y:longint):longint;
var d,i:longint;
begin
if dep[x]<dep[y] then swap(x,y);
d:=dep[x]-dep[y];
for i:= to do
if d and (<<i)> then x:=f[x,i];
for i:= downto do
if f[x,i]<>f[y,i] then
begin
x:=f[x,i]; y:=f[y,i];
end;
if x=y then exit(x);
exit(f[x,]);
end; procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
i:=l; j:=r; mid:=b[(l+r)>>];
repeat
while mid>b[i] do inc(i);
while mid<b[j] do dec(j);
if i<=j then
begin
swap(b[i],b[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end; function lowbit(x:longint):longint;
begin
exit(x and (-x));
end; function query(l,r,k:longint):longint;
var s1,s2,i,mid:longint;
begin
if l=r then exit(l);
mid:=(l+r)>>;
s1:=; s2:=;
for i:= to la do s1:=s1+t[t[q1[i]].l].s;
for i:= to lb do s2:=s2+t[t[q2[i]].l].s;
s2:=s2+t[t[f1].l].s+t[t[f2].l].s;
s1:=s1+t[t[f3].l].s+t[t[f4].l].s;
if s2-s1>=k then
begin
f1:=t[f1].l; f2:=t[f2].l;
f3:=t[f3].l; f4:=t[f4].l;
for i:= to la do q1[i]:=t[q1[i]].l;
for i:= to lb do q2[i]:=t[q2[i]].l;
exit(query(l,mid,k));
end
else
begin
f1:=t[f1].r; f2:=t[f2].r;
f3:=t[f3].r; f4:=t[f4].r;
for i:= to la do q1[i]:=t[q1[i]].r;
for i:= to lb do q2[i]:=t[q2[i]].r;
exit(query(mid+,r,k-(s2-s1)));
end;
end; begin
assign(input,'data.in'); reset(input);
assign(output,'tyvj2133.out'); rewrite(output);
read(n,m);
for i:= to n do
begin
read(a[i]); b[i]:=a[i];
end;
q:=n;
for i:= to n- do
begin
read(x,y);
add(x,y);
add(y,x);
end; for i:= to m do
for j:= to do read(d[i,j]);
for i:= to m do
if d[i,]= then
begin
inc(q); b[q]:=d[i,];
end;
qsort(,q);
hash[]:=b[]; up:=;
for i:= to q do
if b[i]<>b[i-] then begin inc(up); hash[up]:=b[i]; end;
dfs(); for i:= to m do
if d[i,]= then
begin
tmp:=find(a[d[i,]]);
j:=st[d[i,]];
while j<=n do
begin
update(,up,root2[j],tmp,-);
j:=j+lowbit(j);
end;
j:=ed[d[i,]]+;
while j<=n do
begin
update(,up,root2[j],tmp,);
j:=j+lowbit(j);
end;
tmp:=find(d[i,]);
j:=st[d[i,]];
while j<=n do
begin
update(,up,root2[j],tmp,);
j:=j+lowbit(j);
end;
j:=ed[d[i,]]+;
while j<=n do
begin
update(,up,root2[j],tmp,-);
j:=j+lowbit(j);
end; a[d[i,]]:=d[i,];
end
else
begin
la:=; lb:=; p:=lca(d[i,],d[i,]);
j:=st[d[i,]];
while j> do
begin
inc(lb); q2[lb]:=root2[j];
j:=j-lowbit(j);
end; j:=st[d[i,]];
while j> do
begin
inc(lb); q2[lb]:=root2[j];
j:=j-lowbit(j);
end; j:=st[p];
while j> do
begin
inc(la); q1[la]:=root2[j];
j:=j-lowbit(j);
end; j:=st[f[p,]];
while j> do
begin
inc(la); q1[la]:=root2[j];
j:=j-lowbit(j);
end; f1:=root1[d[i,]]; f2:=root1[d[i,]];
f3:=root1[p]; f4:=root1[f[p,]];
sum:=dep[d[i,]]+dep[d[i,]]-dep[p]*+;
z:=sum-d[i,]+;
if sum<d[i,] then writeln('invalid request!')
else writeln(hash[query(,up,z)]);
end; close(input);
close(output);
end.
最新文章
- android 帧动画
- Python环境安装
- SourceForge无法访问的解决办法
- 获取 UIWebView中用户所点击的图片URL
- cocoapods 终极方案
- 使用SQL语句清空数据库所有表的数据
- 【不积跬步，无以致千里】vim复制
- Android：安卓资源引用符号的含义
- Mac下Intellij IDea发布Java Web项目(适合第一次配置Tomcat的家伙们)详解二
- Spring使用小结2
- javabean对象自动赋值给另一个javabean对象
- cocos2d-x游戏开发系列教程-坦克大战游戏之敌方坦克AI的编写
- iOS之网络编程
- shell 中最常使用的 FD (file descriptor)
- IE下 GIF不动失效的奇葩问题
- [USACO 12JAN]Mountain Climbing
- JDK源码中，都有哪些NB的设计模式？
- EF Code First列名 'Discriminator' 无效的问题
- [mongoDB]PyMongo Cursor Not Found Error
- 什么是虚拟DOM?为啥虚拟DOM可以提升性能？