题解

………………………………………………

我莫不是一个智障吧

我把testdata的编号

当成数据组数读进来

我简直有毒

以为哪里写错了自闭了好久

实际上这题很简单，只要愉悦地开个启发式合并，然后每次暴力修改一个点的根缀主席树和倍增lca数组就行

复杂度\(n \log^2 n\)

代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 80005

#define eps 1e-10

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

	res = 0;T f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {x = -x;putchar('-');}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

int N,M,Q;

int val[MAXN],w[MAXN],cnt,fa[MAXN][20],belong[MAXN],siz[MAXN],dep[MAXN];

struct node {

	int sum,lc,rc;

}tr[MAXN * 200];

struct Enode {

	int to,next;

}E[MAXN * 2];

int Ncnt,rt[MAXN],sumE,head[MAXN];

void add(int u,int v) {

	E[++sumE].to = v;

	E[sumE].next = head[u];

	head[u] = sumE;

}

int getfa(int u) {

	return belong[u] == u ? u : belong[u] = getfa(belong[u]);

}

void Insert(const int &x,int &y,int l,int r,int v) {

	y = ++Ncnt;

	tr[y] = tr[x];

	++tr[y].sum;

	if(l == r) return;

	int mid = (l + r) >> 1;

	if(v <= mid) Insert(tr[x].lc,tr[y].lc,l,mid,v);

	else Insert(tr[x].rc,tr[y].rc,mid + 1,r,v);

}

void rebuild(int u,int f) {

	dep[u] = dep[f] + 1;

	Insert(rt[f],rt[u],1,cnt,w[u]);

	fa[u][0] = f;

	for(int i = 1 ; i <= 18 ; ++i) {

		fa[u][i] = fa[fa[u][i - 1]][i - 1];

	}

	for(int i = head[u] ; i ; i = E[i].next) {

		int v = E[i].to;

		if(v != f) rebuild(v,u);

	}

}

void Init() {

	Ncnt = 0;sumE = 0;

	memset(fa,0,sizeof(fa));

	memset(rt,0,sizeof(rt));

	memset(head,0,sizeof(head));

	memset(dep,0,sizeof(dep));

	read(N);read(M);read(Q);

	for(int i = 1 ; i <= N ; ++i) {

		read(w[i]);val[i] = w[i];

	}

	sort(val + 1,val + N + 1);

	cnt = unique(val + 1,val + N + 1) - val - 1;

	for(int i = 1 ; i <= N ; ++i) {

		w[i] = lower_bound(val + 1,val + cnt + 1,w[i]) - val;

	}

	for(int i = 1 ; i <= N ; ++i) belong[i] = i,siz[i] = 1;

	int u,v;

	for(int i = 1 ; i <= M ; ++i) {

		read(u);read(v);

		add(u,v);add(v,u);

		siz[getfa(v)] += siz[getfa(u)];

		belong[getfa(u)] = getfa(v);

	}

	for(int i = 1 ; i <= N ; ++i) {

		if(i == belong[i]) rebuild(i,0);

	}

}

int lca(int u,int v) {

	if(dep[u] < dep[v]) swap(u,v);

	int l = 18;

	while(dep[u] > dep[v]) {

		if(dep[fa[u][l]] >= dep[v]) u = fa[u][l];

		--l;

	}

	if(u == v) return u;

	l = 18;

	while(fa[u][0] != fa[v][0]) {

		if(fa[u][l] != fa[v][l]) {

			u = fa[u][l];

			v = fa[v][l];

		}

		--l;

	}

	return fa[u][0];

}

int Query(int u,int v,int f,int k) {

	int L = 1,R = cnt;

	int t = w[f];

	u = rt[u],v = rt[v],f = rt[f];

	while(L < R) {

		int mid = (L + R) >> 1;

		int s = tr[tr[u].lc].sum - tr[tr[f].lc].sum + tr[tr[v].lc].sum - tr[tr[f].lc].sum;

		if(t >= L && t <= mid) ++s;

		if(s < k) {

			k -= s;

			L = mid + 1;

			u = tr[u].rc;v = tr[v].rc;f = tr[f].rc;

		}

		else {

			R = mid;

			u = tr[u].lc;v = tr[v].lc;f = tr[f].lc;

		}

	}

	return L;

}

void Solve() {

	char op[5];int x,y,k;

	int lastans = 0;

	for(int i = 1 ; i <= Q ; ++i) {

		scanf("%s",op + 1);

		read(x);read(y);

		x ^= lastans;y ^= lastans;

		if(op[1] == 'L') {

			int p = getfa(x),q = getfa(y);

			if(siz[p] > siz[q]) {swap(x,y);swap(p,q);}

			belong[p] = q;siz[q] += siz[p];

			rebuild(x,y);

			add(x,y);add(y,x);

		}

		else {

			read(k);

			k ^= lastans;

			out(lastans = val[Query(x,y,lca(x,y),k)]);enter;

		}

		//out(i);enter;

	}

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	int T;

	read(T);

	Init();

	Solve();

}