题解 P3224 【[HNOI2012]永无乡】

zhengrunzhe · 2018-07-29 14:40:02 · 题解

指针splay来一发

思维各位dalao都讲的很清楚了

每一个岛都建立一个存储重要值的splay

合并直接把小树的每一个节点都insert到大树里就好了

查询就是查排名(注意输出-1…

#include<cstdio>
#include<algorithm>
const int N=100001;
inline int read()
{
    int out=0;char ch=getchar();
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)out=(out<<3)+(out<<1)+ch-48,ch=getchar();
    return out;
}
namespace Splay //Splay
{
    struct tree
    {
        int value,size;
        tree *fa,*son[2];
        inline tree(int key)
        {
            size=1;
            value=key;
            fa=son[0]=son[1]=NULL;
        }
        inline void pushup()
        {
            size=1;
            if (son[0])size+=son[0]->size;
            if (son[1])size+=son[1]->size;
        }
    }*root[N];
    inline bool connection(tree *p)
    {
        if (p&&p->fa)return p->fa->son[1]==p;
    }
    inline void connect(tree *&p,tree *&fa,bool which)
    {
        if (p)p->fa=fa;
        if (fa)fa->son[which]=p;
    }
    inline void rotate(tree *&p)
    {
        tree *fa=p->fa;
        bool lr=connection(p);
        connect(p,fa->fa,connection(fa));
        connect(p->son[lr^1],fa,lr);
        connect(fa,p,lr^1);
        fa->pushup();p->pushup();
    }
    inline void splay(tree *&p,tree *&root)
    {
        for (tree *fa;fa=p->fa;rotate(p))
            if (fa->fa)
                rotate(connection(p)==connection(fa)?fa:p);
        root=p;
    }
    inline void insert(int insertion,tree *&root)
    {
        if (root==NULL)
        {
            root=new tree(insertion);
            return;
        }
        tree *now=root;
        while (1)
        {
            if (now->value==insertion)return;
            tree *fa=now;
            bool direction=fa->value<insertion;
            now=fa->son[direction];
            if (now==NULL)
            {
                now=new tree(insertion);
                connect(now,fa,direction);
                fa->pushup();
                splay(now,root);
                return;
            }
        }
    }
    inline int find_rank(int ranking,tree *root)
    {
        tree *now=root;
        if (root->size<ranking)return 0;
        while (1)
            if (now->son[0]&&ranking<=now->son[0]->size)
                now=now->son[0];
            else
            {
                ranking-=(now->son[0]?now->son[0]->size:0)+1;
                if (!ranking)return now->value;
                now=now->son[1];
            }
    }
    void merge(tree *&p,tree *&root)
    {
        if (p->son[0])merge(p->son[0],root);
        if (p->son[1])merge(p->son[1],root);
        insert(p->value,root);
    }
}using namespace Splay;
namespace Set  //并查集
{
    int fa[N];
    int find(int p)
    {
        return fa[p]==p?p:fa[p]=find(fa[p]);
    }
    inline void Union(int a,int b)
    {
        int f1=find(a),f2=find(b);
        if (f1==f2)return;
        if (root[f1]->size>root[f2]->size)std::swap(f1,f2);
        //默认小树合大树
        fa[f1]=f2;
        merge(root[f1],root[f2]);
    }
}
int n,m,q,num[N]={-1}; //num[x]表示重要值为x的岛屿的编号，注意-1
int main()
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
    {
        Set::fa[i]=i; //记得初始化
        int ranking=read();
        num[ranking]=i;
        insert(ranking,root[i]);
    }
    while (m--)Set::Union(read(),read());
    q=read();
    while (q--)
    {
        char opt;scanf(" %c",&opt);
        int x=read(),y=read();
        if (opt==66)Set::Union(x,y);
        else printf("%d\n",num[find_rank(y,root[Set::find(x)])]); //注意是find(x) 需要访问集合的根
    }
}