P3302 [SDOI2013]森林

P3302 [SDOI2013]森林

链接

分析：

　　每个点建立从当前点向根的主席树，那么可以查询了。

　　考虑修改，启发式合并！

　　开O2才能过。。。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 80005, Log = 17;
struct Edge { int to, nxt; } e[350005];
int head[N], fa[N], f[N][18], disc[N], w[N], siz[N], dep[N], En, Cnt = 1;
int Root[N], sum[N * 300], ls[N * 300], rs[N * 300], Index;

inline void add_edge(int u,int v) {
    ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;
    ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;
}
void Insert(int l,int r,int &now,int pre,int p) {
    if (!now) now = ++Index;
    sum[now] = sum[pre] + 1;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (p <= mid) {
        rs[now] = rs[pre];
        Insert(l, mid, ls[now], ls[pre], p);
    }
    else {
        ls[now] = ls[pre];
        Insert(mid + 1, r, rs[now], rs[pre], p);
    }
}
int query(int l,int r,int x,int y,int p1,int p2,int k) {
    if (l == r) return disc[l];
    int mid = (l + r) >> 1;
    int t = sum[ls[x]] + sum[ls[y]] - sum[ls[p1]] - sum[ls[p2]];
    if (k <= t) return query(l, mid, ls[x], ls[y], ls[p1], ls[p2], k);
    else return query(mid + 1, r, rs[x], rs[y], rs[p1], rs[p2], k - t);
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void dfs(int u,int top) {
    for (int i = 1; i <= Log; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
    siz[top] ++;
    fa[u] = top;
    dep[u] = dep[f[u][0]] + 1;
    Insert(1, Cnt, Root[u], Root[f[u][0]], w[u]);
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == f[u][0]) continue;
        f[v][0] = u;
        dfs(v, top);
    }
}
int LCA(int u,int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int i = Log; ~i; --i) if ((d >> i) & 1) u = f[u][i];
    if (u == v) return u;
    for (int i = Log; ~i; --i) 
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
int main() {
    read();int n = read(), m = read(), Q = read();
    for (int i = 1; i <= n; ++i) disc[i] = w[i] = read(), fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    sort(disc + 1, disc + n + 1);
    for (int i = 2; i <= n; ++i) if (disc[i] != disc[Cnt]) disc[++Cnt] = disc[i];
    for (int i = 1; i <= n; ++i) w[i] = lower_bound(disc + 1, disc + Cnt + 1, w[i]) - disc;
    for (int i = 1; i <= n; ++i) if (!dep[i]) dfs(i, i); 
    
    int ans = 0;char opt[10];
    while (Q --) {
        scanf("%s", opt);
        if (opt[0] == 'Q') {
            int x = read() ^ ans, y = read() ^ ans, k = read() ^ ans;
            int lca = LCA(x, y);
            printf("%d
", ans = query(1, Cnt, Root[x], Root[y], Root[lca], Root[f[lca][0]], k));
        }
        else {
            int x = read() ^ ans, y = read() ^ ans;
            add_edge(x, y);
            int fx = find(x), fy = find(y);
            if (siz[fx] > siz[fy]) swap(fx, fy), swap(x, y);
            f[y][0] = x;
            dfs(y, fx);
        }
    }
    return 0;
}