BZOJ 2733 2733: [HNOI2012]永无乡平衡树启发式合并

Description

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

Input

输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。对于 20%的数据 n≤1000,q≤1000

对于 100%的数据 n≤100000,m≤n，q≤300000

Output

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-1。

Sample Input
5 1

4 3 2 5 1

1 2

Q 3 2

Q 2 1

B 2 3

B 1 5

Q 2 1

Q 2 4

Q 2 3

Sample Output
-1

解法：自己手撸的第一个启发式合并的题目了，好像这个启发式合并还挺快的2333。对于合并两个平衡树，我们可以暴力的将size小的平衡树中的所有节点删掉，然后加入大的平衡树中，因为每个点只可能被删除插入logn次，所以时间复杂度为nlog^2n。

//BZOJ 2733 TREAP + DSU
//其实没这么长的，我的treap模板比较长2333

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, fa[maxn], a[maxn], Root[maxn], id[maxn];
int find_set(int x){if(x == fa[x]) return x; else return fa[x] = find_set(fa[x]);}
namespace multi_treap{
    struct data{
        int l, r, v, size, rnd, w;
    }tree[4000005];
    int size, root;
    void update(int k)
    {
        tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + tree[k].w;
    }
    void rturn(int &k)
    {
        int t = tree[k].l;
        tree[k].l = tree[t].r;
        tree[t].r = k;
        tree[t].size = tree[k].size;
        update(k);
        k = t;
    }
    void lturn(int &k)
    {
        int t = tree[k].r;
        tree[k].r = tree[t].l;
        tree[t].l = k;
        tree[t].size = tree[k].size;
        update(k);
        k=t;
    }
    void insert(int &k, int x)
    {
        if(k == 0)
        {
            size++;
            k = size;
            tree[k].size = tree[k].w = 1;
            tree[k].v = x;
            tree[k].rnd = rand();
            return ;
        }
        tree[k].size++;
        if(tree[k].v==x) tree[k].w++;//每个结点顺便记录下与该节点相同值的数的个数
        else if(x > tree[k].v)
        {
            insert(tree[k].r, x);
            if(tree[tree[k].r].rnd < tree[k].rnd) lturn(k);//维护堆性质
        }
        else
        {
            insert(tree[k].l, x);
            if(tree[tree[k].l].rnd < tree[k].rnd) rturn(k);
        }
    }
    void del(int &k,int x)
    {
        if(k == 0)return;
        if(tree[k].v == x)
        {
            if(tree[k].w > 1)
            {
                tree[k].w--;
                tree[k].size--;
                return;//若不止相同值的个数有多个，删去一个
            }
            if(tree[k].l * tree[k].r == 0)k = tree[k].l + tree[k].r;//有一个儿子为空
            else if(tree[tree[k].l].rnd < tree[tree[k].r].rnd)
                rturn(k),del(k,x);
            else lturn(k),del(k,x);
        }
        else if(x > tree[k].v)
            tree[k].size--, del(tree[k].r,x);
        else tree[k].size--, del(tree[k].l,x);
    }
    int query_rank(int k, int x)
    {
        if(k == 0) return 0;
        if(tree[k].v == x) return tree[tree[k].l].size + 1;
        else if(x > tree[k].v)
            return tree[tree[k].l].size + tree[k].w + query_rank(tree[k].r, x);
        else return query_rank(tree[k].l, x);
    }
    int query_num(int k, int x)
    {
        if(k == 0) return 0;
        if(x <= tree[tree[k].l].size)
            return query_num(tree[k].l, x);
        else if(x > tree[tree[k].l].size + tree[k].w)
            return query_num(tree[k].r,x - tree[tree[k].l].size-tree[k].w);
        else return tree[k].v;
    }
}
using namespace multi_treap;

void combine(int x, int y){
    int fx = find_set(x), fy = find_set(y);
    if(tree[Root[fx]].size < tree[Root[fy]].size) swap(fx, fy); //fx > fy
    fa[fy] = fx;
    if(fx == fy) return ;
    fy = Root[fy];
    while(Root[fy]){
        insert(Root[fx], a[fy]);
        del(Root[fy], a[fy]);
    }
}

void ask(int x, int k){
    x = Root[find_set(x)];
    if(tree[x].size >= k) printf("%d\n", id[query_num(x, k)]);
    else puts("-1");
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) id[a[i]] = i;
    for(int i = 1; i <= n; i++) fa[i] = i, insert(Root[i], a[i]);
    while(m--){
        int x, y;
        scanf("%d%d", &x, &y);
        combine(x, y);
    }
    int T;
    scanf("%d", &T);
    while(T--){
        char s[10]; int x, y;
        scanf("%s%d%d", s, &x, &y);
        if(s[0] == 'B') combine(x, y);
        else ask(x, y);
    }
    return 0;
}

BZOJ 2733 2733: [HNOI2012]永无乡 平衡树启发式合并

BZOJ 2733 2733: [HNOI2012]永无乡平衡树启发式合并