我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树，我们可能可以想到用LCT来维护。但是代码难度太高，而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作，也就是说，每一次，我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树，我们暴力更新其中的每一个节点。于是可以证明，每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意：主席树的L，R本身就是节点位置；合并的时候要记得更新小树的根节点；返回的值是第k大的值而非第k大的排名因而要逆离散化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
const int N=80005;
struct data{
int id;
int val;
}a[N];
inline bool cmp(const data &A,const data &B){
return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
return A.id<B.id;
}
struct ee{
int v;
int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
inline void add(int U,int V){
Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
private:
class Node{
public:
int l;int r;int sz;
};
Node tr[30000000];
int cnt,rt[N];
inline void bld(int LST,int &NW,int L,int R,int V){
NW=++cnt;tr[NW].sz=tr[LST].sz+1;
if(L==R){return;}
V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
}
inline int qry(int A,int B,int C,int D,int L,int R,int V){
while(L<R){
// printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
}
return L;
}
inline void prnt(int X){
if(!X){
return;
}
prnt(tr[X].l);
prnt(tr[X].r);
printf("%d ",tr[X].sz);
}
public:
inline void ADD(int LST,int VER,int V){
bld(rt[LST],rt[VER],1,80000,V);
}
inline int QRY(int A,int B,int C,int D,int V){
return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
}
inline void prpr(){
cnt=0;
}
inline void pt(int X){
prnt(rt[X]);
}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
// printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
vis[X]=sz[X]=1;
for(int i=h[X];i;i=e[i].nxt){
if(vis[e[i].v]){
continue;
}
fa[e[i].v][0]=X;
dep[e[i].v]=dep[X]+1;
for(int j=1;j<=18;++j){
fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
}
TR.ADD(X,e[i].v,a[e[i].v].val);
dfs0(e[i].v);
sz[X]+=sz[e[i].v];
}
}
inline void dfs1(int X){
vis[X]=0;
for(int i=h[X];i;i=e[i].nxt){
if(!vis[e[i].v]){
continue;
}
dfs1(e[i].v);
}
}
inline int szq(int X){
for(int i=18;i>=0;--i){
if(fa[X][i]!=0){
X=fa[X][i];
}
}
return sz[X];
}
inline void uni(int X,int Y){
int SZ=szq(X);
dfs1(X);
add(X,Y);
fa[X][0]=Y;
dep[X]=dep[Y]+1;
TR.ADD(Y,X,a[X].val);
for(int i=1;i<=18;++i){
fa[X][i]=fa[fa[X][i-1]][i-1];
}
int RT=X;
for(int i=18;i>=0;--i){
if(fa[RT][i]){
RT=fa[RT][i];
}
}
sz[RT]+=SZ;
dfs0(X);
}
inline int lca(int X,int Y){
if(dep[X]<dep[Y]){
X^=Y^=X^=Y;
}
for(int i=18;i>=0;--i){
if(dep[fa[X][i]]>=dep[Y]){
X=fa[X][i];
}
}
if(X==Y){
return X;
}
for(int i=18;i>=0;--i){
if(fa[X][i]!=fa[Y][i]){
X=fa[X][i],Y=fa[Y][i];
}
}
return fa[X][0];
}
int n,m,q,tid;
void init(){
scanf("%d",&tid);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i){
scanf("%d",&a[i].val);
a[i].id=i;
}
std::sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i){
loc[i]=a[i].val;
}
for(int i=1;i<=n;++i){
if(a[i].val!=a[i-1].val){
a[i].val=a[i-1].val+1;
}else{
a[i].val=a[i-1].val;
}
}
std::sort(a+1,a+1+n,cmp2);
int u,v;
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);
}
TR.prpr();
for(int i=1;i<=n;++i){
if(!vis[i]){
dep[i]=1;
TR.ADD(0,i,a[i].val);
dfs0(i);
}
}
// for(int i=1;i<n;++i){
// printf("%d:",i);
// TR.pt(i);
// puts("");
// }
int lans=0,x,lc;
char ch[10];
for(int i=1;i<=q;++i){
cin>>ch+1;
switch(ch[1]){
case 'Q':{
scanf("%d%d%d",&u,&v,&x);
u^=lans,v^=lans,x^=lans;
lc=lca(u,v);
// printf("\t\t\t%d %d %d\n",u,v,x);
printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
break;
}
case 'L':{
scanf("%d%d",&u,&v);
u^=lans,v^=lans;
// printf("\t\t\t%d %d\n",u,v);
if(szq(u)>szq(v)){
u^=v^=u^=v;
}
uni(u,v);
break;
}
}
}
}
int main(){
init();
return 0;
}
