【洛谷3224/BZOJ2733】[HNOI2012]永无乡 (Splay启发式合并)

时间:2021-12-06 20:42:21

题目:

洛谷3224

分析:

这题一看\(n\leq100000\)的范围就知道可以暴力地用\(O(nlogn)\)数据结构乱搞啊……

每个联通块建一棵Splay树,查询就是Splay查询第k大的模板,建桥的时候就把两个联通块的Splay进行“启发式合并”

本来以为启发式合并是什么高端的东西,tzh神犇给我说就是把小的推倒然后暴力插入到大的里面2333

初始我给每个岛都建了一棵Splay树,合并\(a\), \(b\)两岛 (\(size_a<size_b\)) 时将\(a\)树插入到\(b\)树中,然后删除\(a\)树。合并两联通块同理。注意由于除了并查集祖先的树,该联通块中其他的树都已经被删除,所以要用并查集辅助记录哪个岛(\(b\))“代表”这个联通块

建桥时一定要判断两个点是否已经在同一联通块内,合并空树会RE!!!

我SB啊因为这个调一下午

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

namespace zyt
{
    const int N = 100010;
    int n, m, rank[N];
    struct Splay
    {
        struct node
        {
            int val, id, size;
            node *fa, *s[2];
            node(node *const f, const int v, const int i):fa(f), val(v), id(i)
            {
                s[0] = s[1] = NULL;
                size = 1;
            }
        }*head;
        void update(node *rot)
        {
            rot->size = 1;
            if (rot->s[0])
                rot->size += rot->s[0]->size;
            if (rot->s[1])
                rot->size += rot->s[1]->size;
        }
        bool dir(const node *rot)
        {
            return rot == rot->fa->s[1];
        }
        void rotate(node *rot)
        {
            node *f = rot->fa, *ff = f->fa;
            bool d = dir(rot);
            rot->fa = ff;
            if (ff)
                ff->s[dir(f)] = rot;
            else
                head = rot;
            f->s[d] = rot->s[!d];
            if (rot->s[!d])
                rot->s[!d]->fa = f;
            f->fa = rot;
            rot->s[!d] = f;
            update(f);
            update(rot);
        }
        void splay(node *rot, const node *goal = NULL)
        {
            while (rot && rot->fa != goal)
            {
                node *f = rot->fa, *ff = f->fa;
                if (ff)
                    if (dir(rot) ^ dir(f))
                        rotate(rot), rotate(rot);
                    else
                        rotate(f), rotate(rot);
                else
                    rotate(rot);
            }
        }
        void insert(const int id, const int val)
        {
            node *rot = head;
            if (rot == NULL)
                head = new node(NULL, val, id);
            else
            {
                while (1)
                {
                    if (val < rot->val)
                        if (rot->s[0])
                            rot = rot->s[0];
                        else
                        {
                            rot->s[0] = new node(rot, val, id);
                            splay(rot->s[0]);
                            break;
                        }
                    else
                        if (rot->s[1])
                            rot = rot->s[1];
                        else
                        {
                            rot->s[1] = new node(rot, val, id);
                            splay(rot->s[1]);
                            break;
                        }
                }
            }
        }
        int find_kth(const int k)
        {
            int tmp = k;
            node *rot = head;
            while(1)
            {
                if (!rot)
                    return -1;
                if ((!rot->s[0] && tmp == 1) || (rot->s[0] && tmp == rot->s[0]->size + 1))
                    return rot->id;
                if (rot->s[0] && tmp <= rot->s[0]->size)
                    rot = rot->s[0];
                else
                {
                    if (rot->s[0])
                        tmp -= rot->s[0]->size;
                    tmp--;
                    rot = rot->s[1];
                }
            }
        }
        friend void merge(Splay &a, Splay &b);
        friend void del(node *rot, Splay &d);
    }island[N];
    inline void merge(Splay &a, Splay &b)
    {
        if (a.head->size > b.head->size)
            swap(a, b);
        del(a.head, b);
        a.head = NULL;
    }
    void del(Splay::node *rot, Splay &d)
    {
        d.insert(rot->id, rot->val);
        if (rot->s[0])
            del(rot->s[0], d);
        if (rot->s[1])
            del(rot->s[1], d);
        delete rot;
    }
    int p[N];
    int find(const int x)
    {
        return x == p[x] ? x : p[x] = find(p[x]);
    }
    void work()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &rank[i]);
            p[i] = i;
            island[i].insert(i, rank[i]);
        }
        while (m--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            int x = find(a), y = find(b);
            if (x == y)
                continue;
            p[x] = y;
            merge(island[x], island[y]);
        }
        int q;
        scanf("%d", &q);
        while (q--)
        {
            char c;
            int a, b;
            do{c = getchar();} while (c != 'B' && c != 'Q');
            scanf("%d%d", &a, &b);
            if (c == 'B')
            {
                int x = find(a), y = find(b);
                if (x == y)
                    continue;
                p[x] = y;
                merge(island[x], island[y]);
            }
            else
                printf("%d\n", island[find(a)].find_kth(b));
        }
    }
}
int main()
{
    zyt::work();
    return 0;
}