题意：一个带点权的森林，要求维护以下操作：
1.询问路径上的点权K大值
2.两点之间连边
n,m<=80000
思路：如果树的结构不发生变化只需要维护DFS序
现在因为树的结构发生变化，要将两棵树合并，这步可以用启发式合并，将比较小的树暴力连接到较大的树上面
离线的LCA算法无法维护，而倍增可以合并，所以用倍增求LCA
其余就是主席树，维护根到点的权值线段树就行了
机房里的罗爷爷写法比我高到不知道哪里去了
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=;
int cas,n,m,q,i,x,y,k,edgenum,cnt,ans;
int a[M],b[M],c[M],head[M],vet[M],next[M],dep[M],fa[M][],f[M],size[M],root[M];
struct node{int l,r,w;}tree[M*];
bool cmp(int x,int y){return a[x]<a[y];}
int search(int x){
if (f[x]!=x)f[x]=search(f[x]);
return f[x];
}
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
void update(int x,int l,int r,int &p){
tree[++cnt]=tree[p];p=cnt;tree[p].w++;
if (l==r)return;
int mid=l+r>>;
if (x<=mid)update(x,l,mid,tree[p].l);
else update(x,mid+,r,tree[p].r);
}
int query(int l,int r,int k,int x,int y,int z,int w){
if (l==r)return l;
int mid=l+r>>,t=tree[tree[x].l].w+tree[tree[y].l].w-tree[tree[z].l].w-tree[tree[w].l].w;
if (t>=k)return query(l,mid,k,tree[x].l,tree[y].l,tree[z].l,tree[w].l);
else return query(mid+,r,k-t,tree[x].r,tree[y].r,tree[z].r,tree[w].r);
}
int lca(int x,int y){
if (dep[x]<dep[y])swap(x,y);
int t=dep[x]-dep[y];
for (int i=;i<=;i++)
if (t&(<<i))x=fa[x][i];
for (int i=;i>=;i--)
if (fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if (x==y)return x;
return fa[x][];
}
void dfs(int u,int pre){
fa[u][]=pre;
for (int i=;i<=;i++)fa[u][i]=fa[fa[u][i-]][i-];
root[u]=root[pre];
update(c[u],,n,root[u]);
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v==pre)continue;
dep[v]=dep[u]+;
dfs(v,u);
}
}
void link(int x,int y){
int p=search(x),q=search(y);
if (size[p]>size[q]){swap(x,y);swap(p,q);}
dep[x]=dep[y]+;
dfs(x,y);
f[p]=q;size[q]+=size[p];
addedge(x,y);
addedge(y,x);
}
int main(){
scanf("%d",&cas);
scanf("%d%d%d",&n,&m,&q);
for (i=;i<=n;i++)scanf("%d",&a[i]),b[i]=i;
sort(b+,b+n+,cmp);
for (i=;i<=n;i++)c[b[i]]=i;
for (i=;i<=n;i++)f[i]=i,size[i]=;
cnt=n;
for (i=;i<=n;i++)root[i]=i,update(c[i],,n,root[i]);
for (i=;i<=m;i++){
scanf("%d%d",&x,&y);
link(x,y);
}
while (q--){
char s[];
scanf("%s",s);
if (s[]=='L'){
scanf("%d%d",&x,&y);
x^=ans;y^=ans;
link(x,y);
}else{
scanf("%d%d%d",&x,&y,&k);
x^=ans;y^=ans;k^=ans;
int z=lca(x,y);
printf("%d\n",ans=a[b[query(,n,k,root[x],root[y],root[z],root[fa[z][]])]]);
}
}
}
这是我的萎靡写法
var t:array[..]of record
l,r,s:longint;
end;
f:array[..,..]of longint;
root,head,c,a,hash,h,dep,stk,size:array[..]of longint;
vet,next:array[..]of longint;
n,m,x,y,z,lastans,i,j,tot,cnt,k,s,up,top,que:longint;
ch:string; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
i:=l; j:=r; mid:=c[(l+r)>>];
repeat
while mid>c[i] do inc(i);
while mid<c[j] do dec(j);
if i<=j then
begin
swap(c[i],c[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 lsh(x:longint):longint;
var l,r,mid:longint;
begin
l:=; r:=up;
while l<=r do
begin
mid:=(l+r)>>;
if x=hash[mid] then exit(mid);
if x<hash[mid] then r:=mid-
else l:=mid+;
end;
end; function find(k:longint):longint;
begin
if h[k]<>k then h[k]:=find(h[k]);
exit(h[k]);
end; procedure add(a,b:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
head[a]:=tot;
end; procedure pushup(p:longint);
begin
t[p].s:=t[t[p].l].s+t[t[p].r].s;
end; procedure update(l,r,x:longint;var y:longint;v:longint);
var mid:longint;
begin
inc(cnt); y:=cnt;
t[y]:=t[x]; inc(t[y].s);
if l=r then exit;
mid:=(l+r)>>;
if v<=mid then update(l,mid,t[x].l,t[y].l,v)
else update(mid+,r,t[x].r,t[y].r,v);
pushup(y);
end; procedure dfs(u,pre:longint);
var e,v,x,y:longint;
begin
update(,up,root[pre],root[u],a[u]);
e:=head[u];
dep[u]:=dep[pre]+;
f[u,]:=pre;
while e<> do
begin
v:=vet[e];
if v<>pre then
begin
dfs(v,u);
x:=find(v); y:=find(u);
if size[x]<size[y] then
begin
size[x]:=size[y]+size[x];
h[y]:=x;
end
else begin size[y]:=size[x]+size[y]; h[x]:=y; end;
end;
e:=next[e];
end;
end; function lca(x,y:longint):longint;
var i,d: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; function query(l,r,x,y,z,w,k:longint):longint;
var mid,tmp:longint;
begin
if l=r then exit(l);
mid:=(l+r)>>;
tmp:=t[t[x].l].s+t[t[y].l].s-t[t[z].l].s-t[t[w].l].s;
if tmp>=k then
begin
x:=t[x].l; y:=t[y].l; z:=t[z].l; w:=t[w].l;
exit(query(l,mid,x,y,z,w,k));
end
else
begin
x:=t[x].r; y:=t[y].r; z:=t[z].r; w:=t[w].r;
exit(query(mid+,r,x,y,z,w,k-tmp));
end;
end; function ask(x,y,z:longint):longint;
var q:longint;
begin
q:=lca(x,y);
exit(hash[query(,up,root[x],root[y],root[q],root[f[q,]],z)]);
end; procedure rebuild(u,pre:longint);
var e,v:longint;
begin
inc(top); stk[top]:=u;
update(,up,root[pre],root[u],a[u]);
dep[u]:=dep[pre]+;
f[u,]:=pre;
e:=head[u];
while e<> do
begin
v:=vet[e];
if v<>pre then rebuild(v,u);
e:=next[e];
end;
end; procedure merge(x,y:longint);
var tx,ty,z,i,j:longint;
begin
tx:=find(x); ty:=find(y);
if size[tx]>size[ty] then
begin
swap(tx,ty); swap(x,y);
end;
top:=;
add(x,y); add(y,x);
rebuild(x,y);
h[tx]:=ty; size[ty]:=size[ty]+size[tx];
for i:= to do
for j:= to top do
begin
z:=stk[j];
f[z,i]:=f[f[z,i-],i-];
end;
end; begin
assign(input,'bzoj3123.in'); reset(input);
assign(output,'bzoj3123.out'); rewrite(output);
readln(x);
readln(n,m,que);
for i:= to n do
begin
read(a[i]);
c[i]:=a[i];
end;
qsort(,n);
up:=; hash[]:=c[];
for i:= to n do
if c[i]<>c[i-] then begin inc(up); hash[up]:=c[i]; end;
for i:= to n do a[i]:=lsh(a[i]);
for i:= to m do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
for i:= to n do
begin
h[i]:=i; size[i]:=;
end;
for i:= to n do
if root[i]= then dfs(i,);
for i:= to do
for j:= to n do f[j,i]:=f[f[j,i-],i-];
for i:= to que do
begin
readln(ch); s:=; k:=length(ch); x:=; y:=; z:=;
for j:= to k do
begin
if ch[j]=' ' then begin if ch[j-]<>' ' then inc(s); continue; end;
if s= then x:=x*+ord(ch[j])-ord('');
if s= then y:=y*+ord(ch[j])-ord('');
if s= then z:=z*+ord(ch[j])-ord('');
end;
if ch[]='Q' then
begin
x:=x xor lastans; y:=y xor lastans; z:=z xor lastans; //writeln(x,' ',y,' ',z);
k:=ask(x,y,z);
writeln(k);
lastans:=k;
end
else
begin
x:=x xor lastans; y:=y xor lastans;// writeln(x,' ',y,' ',z);
merge(x,y);
end; end;
close(input);
close(output);
end.