[BZOJ2733] [HNOI2012]永無鄉 && splay

splay每次把小的樹的每一個元素暴力的插入大的當中 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define SF scanf
#define PF printf
using namespace std;
typedef long long LL;
const int MAXN = 100000;
int f[MAXN+10], n, m;
int find(int x) {
    return x == f[x] ? x : (f[x] = find(f[x]));
}
struct Splay_Tree {
    int root, ncnt;
    int fa[MAXN+10], ch[MAXN+10][2];
    int sz[MAXN+10], val[MAXN+10], Q[MAXN+10];
    void up(int x) {
        if(!x) return ;
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y];
        bool d = x == ch[fa[x]][0];
        if(ch[y][!d] = ch[x][d]) fa[ch[x][d]] = y;
        if(fa[x] = z) ch[z][y == ch[z][1]] = x;
        up(ch[x][d] = y);
        fa[y] = x;
    };
    void splay(int x, int goal) {
        for(int y = fa[x]; y != goal; Rotate(x), y = fa[x])
            if(fa[y] != goal) Rotate((x == ch[y][0]) == (y == ch[fa[y]][0]) ? y : x);
        up(x); if(!goal) root = x;
    }
    void ins(int &x, int pre, int id) {
        if(!x) {
            x = id; fa[x] = pre; sz[x] = 1;
            splay(x, 0); return ;
        }
        if(val[id] <= val[x]) ins(ch[x][0], x, id);
        else ins(ch[x][1], x, id);
        up(x);
    }
    int Find_kth(int x, int k) {
        if(k < 0 || k > sz[x]) return -1;
        while(k <= sz[ch[x][0]] || k > sz[ch[x][0]] + 1)
            if(k <= sz[ch[x][0]]) x = ch[x][0];
            else k -= sz[ch[x][0]] + 1, x = ch[x][1];
        splay(x, 0);
        return x;
    }
    void merge(int x, int y) {
        splay(x, 0); splay(y, 0);
        if(sz[x] > sz[y]) swap(x, y);
        int F = 0, R = 1;
        Q[0] = y; Q[1] = x;
        while(F < R) {
            int x = Q[++F];
            if(ch[x][0]) Q[++R] = ch[x][0];
            if(ch[x][1]) Q[++R] = ch[x][1];
            ch[x][0] = ch[x][1] = 0;
            ins(Q[F-1], 0, x);
        }
    }
} sp;
int main() {
    int q, x, y; char c;
    SF("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        SF("%d", &sp.val[i]);
        f[i] = i; sp.sz[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        SF("%d%d", &x, &y);
        if(find(x) != find(y)) {
            sp.merge(x, y);
            f[find(x)] = find(y);
        }
    }
    SF("%d", &q);
    for(int i = 1; i <= q; i++) {
        SF(" %c%d%d", &c, &x, &y);
        if(c == 'B') {
            if(find(x) != find(y)) {
                sp.merge(x, y);
                f[find(x)] = find(y);
            }
        }
        else {
            sp.splay(x, 0);
            PF("%d\n", sp.Find_kth(x, y));
        }
    }
}