Description:

连边 $+$ 询问路径第 $K$ 小，保证任何时刻图是森林。

$1\le N\le 80000$

Solution:

第 $K​$ 小想到主席树，但主席树是静态的，无法支持连边操作，但看数据范围只有 $80000​$ ，可以每次连边时用启发式合并的思想，暴力将 $siz​$ 小的树中的点挂到另一个树上去，在加点时从父亲继承下来一个版本，在这个版本上加入这个点的值， $LCA​$ 也必须动态求，显然链剖和 $tarjan​$ 都不能用，在挂点时一边 $dfs​$ 一边重新计算倍增数组，询问时树上查分即可。

连边时忘了加边居然有60分

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

#define mid ((l + r) >> 1)

using namespace std;

char getc()

{

    char c = getchar();

    while(c != 'Q' && c != 'L')c = getchar();

    return c;

}

int read()

{

    int res = 0;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

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

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

} 

int testcase;

int n,m,q;

#define MAXN 80001

int siz[MAXN],fa[MAXN],val[MAXN],depth[MAXN];

map<int,int> tr;

int to[MAXN],s[MAXN],tot = 0;

int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;

    e[edgenum].to = b;

    e[edgenum].nxt = lin[a];

    lin[a] = edgenum;

    return;

}

bool v[MAXN];

int f[MAXN][17];

struct node

{

    int c[2],sum;

    node(){c[0] = c[1] = sum = 0;}

}t[MAXN * 500];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

void insert(int &rt,int rt_,int p,int l,int r)

{

    rt = newnode();

    t[rt] = t[rt_];

    t[rt].sum += 1;

    if(l == r)return;

    if(p <= mid)insert(t[rt].c[0],t[rt_].c[0],p,l,mid);

    else insert(t[rt].c[1],t[rt_].c[1],p,mid + 1,r);

    return;

}

void dfs(int k)

{

    v[k] = true;

    for(int i = 1;i <= 16;++i)

    {

        f[k][i] = f[f[k][i - 1]][i - 1];

    }

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != f[k][0])

        {

            f[e[i].to][0] = k;depth[e[i].to] = depth[k] + 1;

            insert(root[e[i].to],root[k],tr[val[e[i].to]],1,tot);

            dfs(e[i].to);

        }

    }

    return;

}

void merge(int a,int b)

{

	add(a,b);add(b,a);

    int p = find(a),q = find(b);

    if(siz[p] > siz[q])

    {

        swap(p,q);swap(a,b);

    }

    fa[p] = q;

    siz[q] += siz[p];

    f[a][0] = b;

    depth[a] = depth[b] + 1;

    insert(root[a],root[b],tr[val[a]],1,tot);

    dfs(a);

    return;

}

int LCA(int a,int b)

{

    if(depth[a] < depth[b])swap(a,b);

    for(int i = 16;i >= 0;--i)

    {

        if(depth[f[a][i]] >= depth[b])

        {

            a = f[a][i];

        }

    }

    if(a == b)return a;

    for(int i = 16;i >= 0;--i)

    {

        if(f[a][i] != f[b][i])

        {

            a = f[a][i];b = f[b][i];

        }

    }

    return f[a][0];

}

int main()

{

    scanf("%d",&testcase);

    scanf("%d%d%d",&n,&m,&q);

    memset(f,0,sizeof(f));

    for(int i = 1;i <= n;++i)

    {

        siz[i] = 1;fa[i] = i;depth[i] = 1;

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

    }

    sort(s + 1,s + 1 + n);

    for(int i = 1;i <= n;++i)

    {

        if(s[i] != s[i - 1])

        {

            tr[s[i]] = ++tot;

            to[tot] = s[i];

        }

    }

    for(int i = 1;i <= n;++i)

    {

        insert(root[i],0,tr[val[i]],1,tot);

    }

    int a,b;

    for(int i = 1;i <= m;++i)

    {

        a = read();b = read();

        merge(a,b);

    }

    memset(v,false,sizeof(v));

    for(int i = 1;i <= n;++i)

    {

        if(!v[i])

        {

            dfs(i);

        }

    }

    int lastans = 0;

    char c;

    int x,y,k;

    int a1,a2,a3,a4;

    for(int i = 1;i <= q;++i)

    {

        c = getc();

        if(c == 'Q')

        {

            x = read();y = read();k = read();

            x ^= lastans;y ^= lastans;k ^= lastans;//cout << x << " " << y << " " << k << endl;

            int lca = LCA(x,y);//cout << " : " << x << " " << y << " " << lca << endl;

            a1 = root[x];a2 = root[y];a3 = root[lca];a4 = root[f[lca][0]];//cout << t[a1].sum << " " << t[a2].sum << " " << t[a3].sum << " " << t[a4].sum << endl;

            int l = 1,r = tot;

            int tmp;

            while(l < r)

            {

                tmp = t[t[a1].c[0]].sum + t[t[a2].c[0]].sum - t[t[a3].c[0]].sum - t[t[a4].c[0]].sum;

                if(k <= tmp)

                {

                    a1 = t[a1].c[0];a2 = t[a2].c[0];a3 = t[a3].c[0];a4 = t[a4].c[0];

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

                }

                else

                {

                    a1 = t[a1].c[1];a2 = t[a2].c[1];a3 = t[a3].c[1];a4 = t[a4].c[1];

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

                    k -= tmp;

                }

            }

            printf("%d\n",lastans = to[l]);

        }

        else

        {

            x = read();y = read();

            x ^= lastans;y ^= lastans;//cout << x << " " << y << endl;

            merge(x,y);

        }

    }

    return 0;

}