[BZOJ4825/Luogu3721][AH2017/HNOI2017]单旋(LCT)

发布于 2018-01-25  98 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4825/Luogu3721][AH2017/HNOI2017]单旋(LCT)

Description

H国是一个热爱写代码的国家,那里的人们很小去学校学习写各种各样的数据结构。伸展树(splay)是一种数据结构,因为代码好写,功能多,效率高,掌握这种数据结构成为了H国的必修技能。有一天,邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说,splay如果写成单旋的,将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理,但还是有H国的人相信了,小H就是其中之一,spaly马上成为他的信仰。而H国的国王,自然不允许这样的风气蔓延,国王构造了一组数据,数据由m(不超过10^5)个操作构成,他知道这样的数据肯定打垮spaly,但是国王还有很多很多其他的事情要做,所以统计每个操作
所需要的实际代价的任务就交给你啦。数据中的操作分为5种:
插入操作:向当前非空spaly中插入一个关键码为key的新孤立节点。插入方法为,先让key和根比较,如果key比根小,则往左子树走,否则往右子树走,如此反复,直到某个时刻,key比当前子树根x小,而x的左子树为空,那就让key成为x的左孩子;或者key比当前子树根x大,而x的右子树为空,那就让key成为x的右孩子。该操作的代价为:插入后,key的深度。特别地,若树为空,则直接让新节点成为一个单个节点的树。(各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。)
单旋最小值:将spaly中关键码最小的元素xmin单旋到根。操作代价为:单旋前xmin的深度。(对于单旋操作的解释见末尾对spaly的描述。)
单旋最大值:将spaly中关键码最大的元素xmax单旋到根。操作代价为:单旋前xmax的深度。
单旋删除最小值:先执行2号操作,然后把根删除。由于2号操作之后,根没有左子树,所以直接切断根和右子树的联系即可。(具体见样例解释)。操作代价同2号操作。
单旋删除最大值:先执行3号操作,然后把根删除。操作代价同3号操作。
对于不是H国的人,你可能需要了解一些spaly的知识,才能完成国王的任务:
spaly是一棵二叉树,满足对于任意一个节点x,它如果有左孩子lx,那么lx的关键码小于x的关键码。如果有右孩子rx,那么rx的关键码大于x的关键码。
一个节点在spaly的深度定义为:从根节点到该节点的路径上一共有多少个节点(包括自己)。
单旋操作是对于一棵树上的节点x来说的。一开始,设f为x在树上的父亲。如果x为f的左孩子,那么执行zig(x)操作(如上图中,左边的树经过zig(x)变为了右边的树),否则执行zag(x)操作(在上图中,将右边的树经过zag(f)就变成了左边的树)。每当执行一次zig(x)或者zag(x),x的深度减小1,如此反复,直到x为根。总之,单旋x就是通过反复执行zig和zag将x变为根。

Http

BZOJ
Luogu

Tag

LCT

解决思路

肯定不能按照题目的意思写一棵\(spaly\),那么我们观察题目的性质,发现每一次都只是修改最小值和最大值。以最小值为例,把最小值\(x\)旋转到根其实只会修改\(x\)、\(x\)的右儿子(如果存在)、\(x\)的父亲和根这四个点,所以直接用\(LCT\)在相应的地方\(Link\)和\(Cut\)即可。而每一次的代价就是这个点到根的距离,在\(LCT\)中\(Split\ x\)和\(spaly\)的根就可以得到啦。
为了方便操作,我们可以在每一个点上在维护\(LCT\)的信息的基础上,维护一下它在\(spaly\)中的左右儿子和父亲,这样就可以直接修改啦。
至于插入的话,因为每一次插入都是插入到\(spaly\)中它的前驱的右儿子或是后继的左儿子,并且可以保证这两个位置一定有一个是空的。那么寻找前驱后继可以用\(Set\)维护值,每一次二分查找出第一个比它大的值,再用\(Map\)维护每一个值对应在\(LCT\)中的编号。
需要注意的是,每一个操作都要特殊判断一下当前点是否为\(spaly\)的根,否则会出错

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int size,rev;
    int sls,srs,sfa;//这三个值分别是spaly中的左右儿子和父亲
};

int root,nodecnt=0;//root记录当前spaly的根
Splay_Data S[maxN];
int Stack[maxN];
set<int> Set;//Set维护前驱后继
map<int,int> Map;//Map维护一个值key对应的点的编号是多少

bool Isroot(int x);
void PushDown(int x);
void Update(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
void Makeroot(int x);
int Findroot(int x);
void Cut(int x,int y);
void Link(int x,int y);
void Insert(int key);
void Splay_min();
void Splay_max();
void Delete_min();
void Delete_max();

int main()
{
    int Q;scanf("%d",&Q);
    while (Q--)
    {
        int c,key;scanf("%d",&c);
        if (c==1) {scanf("%d",&key);Insert(key);}
        if (c==2) Splay_min();
        if (c==3) Splay_max();
        if (c==4) Delete_min();
        if (c==5) Delete_max();
        //cout<<"finish!"<<endl;
    }
    return 0;
}

bool Isroot(int x)
{
    int fa=S[x].fa;
    if ((S[fa].ch[0]==x)||(S[fa].ch[1]==x)) return 0;
    return 1;
}

void PushDown(int x)
{
    if (S[x].rev)
    {
        S[x].rev=0;
        int ls=S[x].ch[0],rs=S[x].ch[1];
        swap(S[ls].ch[0],S[ls].ch[1]);swap(S[rs].ch[0],S[rs].ch[1]);
        if (ls) S[ls].rev^=1;
        if (rs) S[rs].rev^=1;
    }
    return;
}

void Update(int x)
{
    S[x].size=S[S[x].ch[0]].size+S[S[x].ch[1]].size+1;
    return;
}

void Rotate(int x)
{
    int y=S[x].fa,z=S[y].fa;
    int sx=(x==S[y].ch[1]);
    int sy=(y==S[z].ch[1]);
    S[x].fa=z;if (Isroot(y)==0) S[z].ch[sy]=x;
    S[y].ch[sx]=S[x].ch[sx^1];if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;
    S[y].fa=x;S[x].ch[sx^1]=y;
    Update(y);return;
}

void Splay(int x)
{
    int now=x,stacktop=1;Stack[1]=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=S[now].fa;now=S[now].fa;
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=S[x].fa,z=S[y].fa;
        if (Isroot(y)==0)
            ((x==S[y].ch[0])^(y==S[z].ch[0]))?(Rotate(x)):(Rotate(y));
        Rotate(x);
    }
    Update(x);return;
}

void Access(int x)
{
    int lastx=0;
    while (x)
    {
        Splay(x);S[x].ch[1]=lastx;Update(x);
        lastx=x;x=S[x].fa;
    }
    return;
}

void Makeroot(int x)
{
    Access(x);Splay(x);S[x].rev^=1;swap(S[x].ch[0],S[x].ch[1]);
    return;
}

int Findroot(int x)
{
    Access(x);Splay(x);
    while (S[x].ch[0]) x=S[x].ch[0];
    return x;
}

void Cut(int x,int y)
{
    Makeroot(x);Access(y);Splay(y);
    if (S[y].ch[0]!=x) return;
    S[x].fa=S[y].ch[0]=0;
    return;
}

void Link(int x,int y)
{
    Makeroot(x);S[x].fa=y;
    return;
}

void Insert(int key)
{
    nodecnt++;S[nodecnt].size=1;Map[key]=nodecnt;
    if (Set.empty())//若set为空,说明树空,直接插入即可
    {
        Set.insert(key);root=nodecnt;printf("1\n");
        return;
    }
    set<int>::iterator pos=Set.lower_bound(key);//由于题目保证了关键码不重复,所以lower_bound找到的是第一个大于key的位置,即key的后继
    if ((pos==Set.end())||(S[Map[*pos]].sls!=0))//到了最后一个,或者是后继的左儿子非空,那么放到前驱的右儿子
    {
        pos--;//找到前驱
        S[Map[*pos]].srs=nodecnt;S[nodecnt].sfa=Map[*pos];
        Link(nodecnt,Map[*pos]);
    }
    else//否则放到后继的左儿子
    {
        S[Map[*pos]].sls=nodecnt;S[nodecnt].sfa=Map[*pos];
        Link(nodecnt,Map[*pos]);
    }
    Set.insert(key);
    Makeroot(nodecnt);Access(root);Splay(root);
    printf("%d\n",S[root].size);
    return;
}

void Splay_min()
{
    int key=*Set.begin();//找到最小值
    int pos=Map[key];//找到最小值在LCT中的编号
    if (root==pos) {printf("1\n");return;}
    Makeroot(pos);Access(root);Splay(root);//查询代价
    printf("%d\n",S[root].size);
    Cut(pos,S[pos].sfa);if (S[pos].srs) Cut(pos,S[pos].srs);//把pos与pos的父亲、pos的右儿子断开
    Link(pos,root);if (S[pos].srs) Link(S[pos].sfa,S[pos].srs);//把pos与root连接,把pos的右儿子和pos的原父亲接上
    S[root].sfa=pos;//更新spaly中的信息
    S[S[pos].sfa].sls=S[pos].srs;if (S[pos].srs) S[S[pos].srs].sfa=S[pos].sfa;
    S[pos].sfa=0;S[pos].srs=root;
    root=pos;return;
}

void Splay_max()
{
    int key=*(--Set.end());
    int pos=Map[key];
    if (root==pos) {printf("1\n");return;}
    Makeroot(pos);Access(root);Splay(root);
    printf("%d\n",S[root].size);
    Cut(S[pos].sfa,pos);if (S[pos].sls) Cut(S[pos].sls,pos);
    Link(pos,root);if (S[pos].sls) Link(S[pos].sfa,S[pos].sls);
    S[root].sfa=pos;
    S[S[pos].sfa].srs=S[pos].sls;if (S[pos].sls) S[S[pos].sls].sfa=S[pos].sfa;
    S[pos].sfa=0;S[pos].sls=root;
    root=pos;return;
}

void Delete_min()
{
    int key=*Set.begin();
    int pos=Map[key];
    Set.erase(Set.begin());
    if (pos==root)
    {
        printf("1\n");
        S[S[pos].srs].sfa=0;
        if (S[pos].srs) Cut(pos,S[pos].srs);
        root=S[pos].srs;
        return;
    }
    Makeroot(pos);Access(root);Splay(root);
    printf("%d\n",S[root].size);
    Cut(pos,S[pos].sfa);if (S[pos].srs) Cut(pos,S[pos].srs);
    if (S[pos].srs) Link(S[pos].sfa,S[pos].srs);
    S[S[pos].sfa].sls=S[pos].srs;if (S[pos].srs) S[S[pos].srs].sfa=S[pos].sfa;
    return;
}

void Delete_max()
{
    int key=*(--Set.end());
    int pos=Map[key];
    Set.erase(--Set.end());
    if (pos==root)
    {
        printf("1\n");
        S[S[pos].sls].sfa=0;
        if (S[pos].sls) Cut(pos,S[pos].sls);
        root=S[pos].sls;
        return;
    }
    Makeroot(pos);Access(root);Splay(root);
    printf("%d\n",S[root].size);
    Cut(pos,S[pos].sfa);if (S[pos].sls) Cut(pos,S[pos].sls);
    if (S[pos].sls) Link(S[pos].sls,S[pos].sfa);
    S[S[pos].sfa].srs=S[pos].sls;if (S[pos].sls) S[S[pos].sls].sfa=S[pos].sfa;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4825/Luogu3721][AH2017/HNOI2017]单旋(LCT)


HNCJ OIer