【BZOJ2733】[HNOI2012] 永无乡（启发式合并Splay）

点此看题面

大致题意： 给你一张图，其中每个点有一个权值，有两种操作：在两点之间连一条边，询问一个点所在联通块第\(k\)小的权值。

平衡树

看到第\(k\)小，应该不难想到平衡树。

为了练习\(Splay\)，所以我是用\(Splay\)来做这题的。

对于询问操作

对于询问操作，我们只要找到该节点所在\(Splay\)的根，然后查询第\(k\)小的权值即可，应该是\(Splay\)比较模板的操作吧。

因此就不多说了。

下面让我们来重点看一看连边操作。

对于连边操作

这才是真正恶心的操作。

考虑这条边连接的两个节点如果是在同一联通块，则完全不必考虑这条边。

但如果连接的是两个联通块，我们就需要合并这两个\(Splay\)。

至于如何合并，自然是启发式合并了。

而启发式合并的操作其实也非常简单，就是遍历较小的\(Splay\)，然后把它里面的节点一个一个插入至较大的\(Splay\)中。

这样的时间复杂度看似极高，实际上均摊之后依然是可以接受的。

具体实现可以见代码。

代码

#include<bits/stdc++.h>

#define N 100000

#define M 300000

#define ull unsigned long long

#define swap(x,y) (x^=y^=x^=y)

using namespace std;

int n,m,a[N+5];

class FIO

{

    private:

        #define Fsize 100000

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)

        #define pc(ch) (void)(FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))

        int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];

    public:

        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}

        inline void read_alpha(char &x) {while(!isalpha(x=tc()));}

        inline void writeln(int x) {if(!x) return pc('0'),pc('\n');if(x<0) pc('-'),x=-x;while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);pc('\n');}

        inline void clear() {fwrite(Fout,1,FoutSize,stdout);}

}F;

class Class_splay//Splay模板

{

    private:

        #define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+1)

        #define Which(x) (node[node[x].Father].Son[1]==x)

        #define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)

        int rt,tot,data[N+5];

        struct Tree

        {

            int Size,Father,Son[2];

            inline void Clear() {Size=1,Father=Son[0]=Son[1]=0;}

        }node[(N+M<<1)+5];

        inline void Rotate(int x,int &k)

        {

            register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);

            (fa^k?node[pa].Son[Which(fa)]=x:k=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);

        }

        inline void Splay(int x,int &k) {for(register int fa=node[x].Father;x^k;Rotate(x,k),fa=node[x].Father) if(fa^k) Rotate(Which(x)^Which(fa)?x:fa,k);}

        inline void Insert(int &x,int pos,int lst)

        {

            if(!x) return (void)(node[x=pos].Clear(),node[x].Father=lst);

            Insert(node[x].Son[a[x]<a[pos]],pos,x),PushUp(x);

        }

        inline void dfs(int x,int rt)//遍历较小的Splay，将其节点一个个插入较大的Splay中

        {

        	if(node[x].Son[0]) dfs(node[x].Son[0],rt);

        	if(node[x].Son[1]) dfs(node[x].Son[1],rt);

        	Insert(rt,x,0),Splay(x,rt);//插入

        }

    public:

    	inline void Init() {for(register int i=1;i<=n;++i) node[i].Size=1;}

        inline void Union(int x,int y)//启发式合并x和y

        {

            while(node[x].Father) x=node[x].Father;//找到根节点

            while(node[y].Father) y=node[y].Father;//找到根节点

            if(!(x^y)) return;//如果在同一个联通块内就退出函数

            if(node[x].Size<node[y].Size) swap(x,y);

            dfs(y,x);

        }

        inline int get_val(int x,int rk)

        {

            while(node[x].Father) x=node[x].Father;

            if(node[x].Size<rk) return -1;

            while(x)

            {

                if(node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];

                else if(node[node[x].Son[0]].Size+1==rk) return x;

                else rk-=node[node[x].Son[0]].Size+1,x=node[x].Son[1];

            }

        }

}splay;

int main()

{

    register int i,Q,x,y;register char op;

    for(F.read(n),F.read(m),i=1;i<=n;++i) F.read(a[i]);

    for(splay.Init(),i=1;i<=m;++i) F.read(x),F.read(y),splay.Union(x,y);

    for(F.read(Q);Q;--Q)

    {

        if(F.read_alpha(op),F.read(x),F.read(y),op^'Q') splay.Union(x,y);

        else F.writeln(splay.get_val(x,y));

    }

    return F.clear(),0;

}

巴特西

【BZOJ2733】[HNOI2012] 永无乡（启发式合并Splay）

平衡树

对于询问操作

对于连边操作

代码

最新文章

热门文章