hash 动开 BIT 启发式合并在这题跑得意外的快。

在码长和用时上几乎是碾压大部分做法的。

求问理论复杂度。

#include <cstdio>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
char o;
int n, m, q, a[100050], f[100050];
__gnu_pbds::gp_hash_table<int, int> c[100050];
int F(int x) { return x == f[x] ? x : f[x] = F(f[x]); }
int G(int x, int y) { return c[x].find(y) != c[x].end() ? c[x][y] : 0; }
void M(int x, int y)
{
    int u = F(x), v = F(y);
    if (c[u].size() > c[v].size())
        swap(u, v);
    f[u] = v;
    for (auto [x, y] : c[u])
        c[v][x] += y;
    c[u].clear();
}
int main()
{
    scanf("%d%d", &n, &m);
    a[n + 1] = -1;
    for (int i = 1, x; i <= n; ++i)
    {
        scanf("%d", &x);
        f[i] = a[x] = i;
        for (int k = x; k <= n; k += k & -k)
            ++c[i][k];
    }
    for (int i = 0, u, v; i < m; ++i)
        scanf("%d%d", &u, &v), M(u, v);
    scanf("%d", &q);
    for (int i = 0, x, y, r, s; i < q; ++i)
    {
        scanf(" %c%d%d", &o, &x, &y);
        if (o == 'Q')
        {
            x = F(x);
            r = s = 0;
            for (int k = 20, a, b; k >= 0; --k)
                if ((a = r + (1 << k)) <= n && (b = s + G(x, a)) < y)
                    r = a, s = b;
            printf("%d\n", a[r + 1]);
        }
        else
            M(x, y);
    }
    return 0;
}

粉兔锐评动开 BIT：蠢。