题意
有一个森林，初始有一定的边。给定两种操作：
-
查询两点路径上k小值。
-
联通两点。
强制在线。
思路
维护主席树，合并的时候按照子树大小dfs暴力合。
代码
学校OJ AC BZOJ MLE Luogu MLE
（然而学校OJ空间限制比洛谷小一半？？？）
#include <bits/stdc++.h>
using namespace std;
namespace StandardIO {
template<typename T>inline void read (T &x) {
x=0;T f=1;char c=getchar();
for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T>inline void write (T x) {
if (x<0) putchar('-'),x*=-1;
if (x>=10) write(x/10);
putchar(x%10+'0');
}
}
using namespace StandardIO;
namespace Project {
const int N=80001;
int n,m,t,len,last;
int a[N],b[N],fa[N],size[N];
int cnt;
int head[N];
struct node {
int to,next;
} edge[N<<2];
int dep[N],vis[N],f[N][17];
int tot;
int root[N];
struct tnode {
int ls,rs;
int size;
} tree[N*600];
inline void add (int a,int b) {
edge[++cnt].to=b,edge[cnt].next=head[a],head[a]=cnt;
}
int find (int x) {
return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void build (int l,int r,int &pos) {
pos=++tot,tree[pos].size=0;
if (l==r) return;
int mid=(l+r)>>1;
build(l,mid,tree[pos].ls),build(mid+1,r,tree[pos].rs);
}
void update (int l,int r,int x,int las,int &pos) {
pos=++tot,tree[pos]=tree[las],++tree[pos].size;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) update(l,mid,x,tree[las].ls,tree[pos].ls);
else update(mid+1,r,x,tree[las].rs,tree[pos].rs);
}
int query (int l,int r,int x,int o,int p,int q,int s) {
if (l==r) return b[l];
int t=tree[tree[o].ls].size+tree[tree[p].ls].size-tree[tree[q].ls].size-tree[tree[s].ls].size,mid=(l+r)>>1;
if (x<=t) return query(l,mid,x,tree[o].ls,tree[p].ls,tree[q].ls,tree[s].ls);
return query(mid+1,r,x-t,tree[o].rs,tree[p].rs,tree[q].rs,tree[s].rs);
}
void dfs (int now,int father,int rt) {
++size[rt],dep[now]=dep[father]+1,fa[now]=father,vis[now]=1,f[now][0]=father;
for (register int i=1; i<=16; ++i) f[now][i]=f[f[now][i-1]][i-1];
update(1,len,lower_bound(b+1,b+len+1,a[now])-b,root[father],root[now]);
for (register int i=head[now]; i; i=edge[i].next) {
int to=edge[i].to;
if (to==father) continue;
dfs(to,now,rt);
}
}
inline int lca (int x,int y) {
if (x==y) return x;
if (dep[x]<dep[y]) swap(x,y);
for (register int i=16; i>=0; --i) {
if (dep[y]<=dep[f[x][i]]) x=f[x][i];
}
if (x==y) return x;
for (register int i=16; i>=0; --i) {
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
inline void MAIN () {
read(n),read(n),read(m),read(t);
for (register int i=1; i<=n; ++i) read(a[i]),b[i]=a[i],fa[i]=i;
sort(b+1,b+n+1),len=unique(b+1,b+n+1)-b-1;
for (register int i=1; i<=m; ++i) {
int x,y;read(x),read(y);
add(x,y),add(y,x);
}
build(1,len,root[0]);
for (register int i=1; i<=n; ++i) {
if (!vis[i]) dfs(i,0,i),fa[i]=i;
}
while (t--) {
char op;int x,y,z;
scanf("%c",&op),read(x),read(y),x^=last,y^=last;
if (op=='Q') {
read(z),z^=last;
int tmp=lca(x,y);
write(last=query(1,len,z,root[x],root[y],root[tmp],root[f[tmp][0]])),putchar('
');
} else {
add(x,y),add(y,x);
int fx=find(x),fy=find(y);
if (size[fx]<size[fy]) swap(fx,fy),swap(x,y);
dfs(y,x,fx);
}
}
}
}
int main () {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Project::MAIN();
}