思路：动态开点的权值线段树，对于每个连通块开一个动态开点的权值线段树，在权值线段树上查询答案。

MLE了3个点QAQ

记录

#include <iostream>
#include <vector>
#include <list>
using namespace std;
struct Node
{
    int data;
    bool end;
    list<Node>::iterator leftChild;
    list<Node>::iterator rightChild;
};
struct Edge
{
    int to;
    Edge *nextEdge;
};
list<Edge> edges;
vector<Edge *> head;
list<Node> tree;
vector<list<Node>::iterator> roots;
vector<int> father;
vector<int> p;
vector<int> p_to_N;
// vector<bool> vir;
int N, M, Q;
void AddEdge(const int &from, const int &to)
{
    edges.push_back({to, head[from]});
    head[from] = &edges.back();
}
void AddData(list<Node>::iterator node, const int &l, const int &r, const int &d)
{
    if (l == r && r == d)
    {
        node->data++;
    }
    else if (l > d || r < d)
    {
        return;
    }
    else
    {
        if (node->end) // 动态开点
        {
            tree.push_back({0});
            tree.back().data = 0;
            tree.back().end = 1;
            node->leftChild = tree.end();
            node->leftChild--;
            tree.push_back({0});
            tree.back().data = 0;
            tree.back().end = 1;
            node->rightChild = tree.end();
            node->rightChild--;
            node->end = 0;
        }
        int mid = (l + r) / 2;
        AddData(node->leftChild, l, mid, d);
        AddData(node->rightChild, mid + 1, r, d);
        node->data = node->leftChild->data + node->rightChild->data;
    }
}
void UnionTree(list<Node>::iterator node1, list<Node>::iterator node2)
{
    if (node2->end)
    {
        node1->data += node2->data;
    }
    else
    {
        if (node1->end) // 动态开点
        {
            tree.push_back({0});
            tree.back().data = 0;
            tree.back().end = 1;
            node1->leftChild = tree.end();
            node1->leftChild--;
            tree.push_back({0});
            tree.back().data = 0;
            tree.back().end = 1;
            node1->rightChild = tree.end();
            node1->rightChild--;
            node1->end = 0;
        }
        UnionTree(node1->leftChild, node2->leftChild);
        UnionTree(node1->rightChild, node2->rightChild);
        node1->data = node1->leftChild->data + node1->rightChild->data;
    }
    tree.erase(node2); // 清除原来的点
}
int FindRoot(const int &x)
{
    return (father[x] ? father[x] = FindRoot(father[x]) : x);
}
bool UnionNode(int x, int y, const bool &toTree)
{
    x = FindRoot(x);
    y = FindRoot(y);
    if (x == y)
    {
        return 1;
    }
    else
    {
        if (toTree) // 需要线段树合并
        {
            UnionTree(roots[y], roots[x]);
        }
        father[x] = y;
        return 0;
    }
}
int FindAns(list<Node>::iterator node, const int &l, const int &r, const int &f)
{
    if (l == r)
    {
        return l;
    }
    else
    {
        if (node->end)
        {
            tree.push_back({0});
            tree.back().end = 1;
            node->leftChild = tree.end();
            node->leftChild--;
            tree.push_back({0});
            tree.back().end = 1;
            node->rightChild = tree.end();
            node->rightChild--;
            node->end = 0;
        }
        int mid = (l + r) / 2;
        if (node->leftChild->data >= f)
        {
            return FindAns(node->leftChild, l, mid, f);
        }
        else
        {
            return FindAns(node->rightChild, mid + 1, r, f - node->leftChild->data);
        }
    }
}
void DFS(const int &n, const int &f, list<Node>::iterator root)
{
    AddData(root, 1, N, p[n]);
    //    vir[n] = true;
    for (Edge *e = head[n]; e != NULL; e = e->nextEdge)
    {
        if (e->to != f)
        {
            DFS(e->to, n, root);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    // vir.assign(N + 1, 0);
    roots.resize(N + 1);
    p.assign(N + 1, 0);
    father.assign(N + 1, 0);
    p_to_N.assign(N + 1, 0);
    head.assign(N + 1, NULL);
    for (int i = 1; i <= N; i++)
    {
        cin >> p[i];
        p_to_N[p[i]] = i;
        tree.push_back({0});
        tree.back().data = 0;
        tree.back().end = 1;
        roots[i] = tree.end();
        roots[i]--;
    }
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        if (!UnionNode(a, b, 0))
        {
            AddEdge(a, b);
            AddEdge(b, a);
        }
    }
    char OP;
    int a, b;
    cin >> Q;
    while (Q) // 运行至第一次查询操作为止，先建立边
    {
        Q--;
        cin >> OP >> a >> b;
        if (OP == 'Q')
        {
            for (int i = 1; i <= N; i++) // 建立线段树
            {
                if (!father[i])
                {
                    DFS(i, 0, roots[i]);
                }
            }
            int r = FindRoot(a);
            if (roots[r]->data < b)
            {
                cout << -1 << endl;
            }
            else
            {
                int ans = FindAns(roots[r], 1, N, b);
                cout << p_to_N[ans] << endl;
            }
            break;
        }
        else
        {
            if (!UnionNode(a, b, 0))
            {
                AddEdge(a, b);
                AddEdge(b, a);
            }
        }
    }
    while (Q)
    {
        Q--;
        cin >> OP >> a >> b;
        if (OP == 'Q')
        {
            int r = FindRoot(a);
            if (roots[r]->data < b) // 点不存在
            {
                cout << -1 << endl;
            }
            else
            {
                int ans = FindAns(roots[r], 1, N, b);
                cout << p_to_N[ans] << endl;
            }
        }
        else
        {
            UnionNode(a, b, 1);
        }
    }
    return 0;
}