http://www.lydsy.com/JudgeOnline/problem.php?id=3123 (题目链接)
题意
给出$n$个点的森林，每个点有一个非负点权，$m$个操作。连接两个点，查询两个点之间路径上的第$K$大点权。强制在线。
Solution
主席树+启发式合并。
对于查询操作，主席树维护区间第$K$大即可，当前节点新建的节点是在其父亲节点基础上建立的，也就是说这个主席树维护的是到根的路径。
对于连接操作，直接启发式合并暴力搞过去就可以了，记得同时更新$size$和$fa$以及重建主席树。
细节
原来不是多组数据，只是当前数据对应的是数据范围的第几个部分分，好良心的主题人啊→_→
果然using namespace 就清晰很多，调过样例就直接过了。
代码
// bzoj3123
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define lim 1000000000
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int maxn=100010;
int Dargen[maxn],size[maxn],deep[maxn],head[maxn],fa[maxn][30],bin[30];
int n,m,Q,sz,ans,cnt,a[maxn],rt[maxn];
struct edge {int to,next;}e[maxn<<1];
struct node {
int son[2],s;
void clear() {son[0]=son[1]=0;s=0;}
int& operator [] (int x) {return son[x];}
}tr[maxn*40];
namespace Chairtree {
void build(int &u,int v,int l,int r,int val) {
if (!u) u=++sz;
if (l==r) {tr[u].s=tr[v].s+1;return;}
int mid=(l+r)>>1;
if (val<=mid) build(tr[u][0],tr[v][0],l,mid,val),tr[u][1]=tr[v][1];
else build(tr[u][1],tr[v][1],mid+1,r,val),tr[u][0]=tr[v][0];
tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s;
}
void merge(int x,int y) {
build(rt[x],rt[y],0,lim,a[x]);
Dargen[x]=Dargen[y];fa[x][0]=y;
deep[x]=deep[y]+1;
for (int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {
merge(e[i].to,x);
size[x]+=size[e[i].to];
}
}
int query(int u,int v,int w,int x,int l,int r,int K) {
if (l==r) return l;
int mid=(l+r)>>1,c=tr[tr[u][0]].s+tr[tr[v][0]].s-tr[tr[w][0]].s-tr[tr[x][0]].s;
if (c>=K) return query(tr[u][0],tr[v][0],tr[w][0],tr[x][0],l,mid,K);
else return query(tr[u][1],tr[v][1],tr[w][1],tr[x][1],mid+1,r,K-c);
}
}
using namespace Chairtree;
namespace Tree {
void link(int u,int v) {
e[++cnt]=(edge){v,head[u]};head[u]=cnt;
e[++cnt]=(edge){u,head[v]};head[v]=cnt;
}
void dfs(int x) {
size[x]=1;build(rt[x],rt[fa[x][0]],0,lim,a[x]);
Dargen[x]=fa[x][0] ? Dargen[fa[x][0]] : x;
for (int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {
fa[e[i].to][0]=x;
deep[e[i].to]=deep[x]+1;
dfs(e[i].to);
size[x]+=size[e[i].to];
}
}
int lca(int x,int y) {
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=0;bin[i]<=t;i++) if (bin[i]&t) x=fa[x][i];
for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return x==y ? x : fa[x][0];
}
}
using namespace Tree;
int main() {
char ch[10];int T;scanf("%d",&T);
bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
scanf("%d%d%d",&n,&m,&Q);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int u,v,i=1;i<=m;i++) {
scanf("%d%d",&u,&v);
link(u,v);
}
for (int i=1;i<=n;i++) if (!size[i]) dfs(i);
for (int x,y,K,i=1;i<=Q;i++) {
scanf("%s%d%d",ch,&x,&y);
x^=ans,y^=ans;
if (ch[0]=='L') {
link(x,y);
if (size[Dargen[x]]>size[Dargen[y]]) swap(x,y);
size[Dargen[y]]+=size[Dargen[x]];
merge(x,y);
}
if (ch[0]=='Q') {
scanf("%d",&K);
K^=ans;
int f=lca(x,y);
ans=query(rt[x],rt[y],rt[f],rt[fa[f][0]],0,lim,K);
printf("%d
",ans);
}
}
return 0;
}