单旋

在我的后园,可以看见墙外有两株树,一株是伸展树,还有一株也是伸展树

——-鲁迅



题意:

​ 如果Splay丧失了双旋的特性,只能单旋,那他就会成为一棵…

​ 然而世界上竟然有人专门用这种数据结构来坑你。

​ 给你一个Spaly,让你求每次给定操作的时间花费。

​ 给定的操作包括:

  • 插入一个点(按两两不同的优先级排序)
  • 旋转最大值至根
  • 旋转最小值至根
  • 旋转最大值至根并删除
  • 旋转最小值至根并删除

分析:

​ 显然,直接模拟这种数据结构会耗尽你的人生。所以我们必须用更加优秀的数据结构来维护这虚伪的Spaly的形态。比如Splay。

​ 假设我们有一棵Spaly,进行单旋时,并不会破坏其二叉树的排序特性,所以我们知道其DFS序是不会改变的。所以我们其实可以用一棵Splay维护其dfs序,同时维护Spaly的形态。这样我们就可以以很高的效率保存并修改一个Spaly。下面,我们需要知道Spaly的旋转如何对应Splay上的修改。

​ 观察发现,将Spaly的最小节点x旋转只根,相对关系改变的节点有$X、ROOT、son[X]、fa[X]$。所以我们将Splay中维护的相关域修改即可。当然,节点相对位置的不变也是导致Spaly如此低效的原因,从“Spaly为啥慢”这个方向入手也可以获得“节点相对位置不变”这个启发。

​ 从这简短的分析可以见得HNOI2017DAY1T1的思维难度并不是很高,而对我来说这题真正的挑战在于代码复杂度和细节。

细节:

​ 首先由于要维护的域比较多,各个域的更新顺序和对于NULL的特判比较复杂,所以难以调试和查错。

​ 比如对于NULL的特判:

void rside(int sd)
{
  ...
  if(!fa)return;
  if(sa)tre[sa].rf=fa;
  ...
}

​ 还有旋旋更健康:

void rside(int sd)
{
  ...
  splay(suf(root,tre[sa].x-1),0);
  ...
}

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 102313

using namespace std;

struct node
{
    int x;
    int rf,rs[2],d,l;
    int f,s[2];
}tre[MX];
int n,cnt,root,rroot,COST;

int pos(int a){return (tre[tre[a].f].s[1]==a);}

void psd(int a)
{
    if(!tre[a].l)return;
    int ls=tre[a].s[0],rs=tre[a].s[1],l=tre[a].l;
    if(ls)tre[ls].d+=l,tre[ls].l+=l;
    if(rs)tre[rs].d+=l,tre[rs].l+=l;
    tre[a].l=0;
}

void rot(int a)
{
    int f=tre[a].f,g=tre[f].f,p=pos(a),q=pos(f);
    tre[f].s[p]=tre[a].s[!p],tre[a].s[!p]=f,tre[f].f=a;
    if(tre[f].s[p])tre[tre[f].s[p]].f=f;
    if(tre[a].f=g)tre[g].s[q]=a;
}

void splay(int a,int tar)
{
    while(tre[a].f!=tar)
        if(tre[tre[a].f].f==tar)rot(a);
        else if(pos(a)==pos(tre[a].f))rot(tre[a].f),rot(a);
        else rot(a),rot(a);
    if(!tar)root=a;
}

int pre(int a,int x)
{
    psd(a);
    if(!a)return 0;
    else if(x<=tre[a].x)return pre(tre[a].s[0],x);
    else
    {
        int ret=pre(tre[a].s[1],x);
        if(ret&&tre[ret].x>tre[a].x)return ret;
        else return a;
    }
}

int suf(int a,int x)
{
    psd(a);
    if(!a)return 0;
    else if(x>=tre[a].x)return suf(tre[a].s[1],x);
    else
    {
        int ret=suf(tre[a].s[0],x);
        if(ret&&tre[ret].x<tre[a].x)return ret;
        else return a;
    }
}

void insrt(int &a,int f,int x)
{
    psd(a);
    if(!a)
    {
        int p=pre(root,x),q=suf(root,x);
        a=++cnt;
        if(tre[p].d>tre[q].d)tre[a].rf=p,tre[a].d=tre[p].d+1,tre[p].rs[1]=a;
        else tre[a].rf=q,tre[a].d=tre[q].d+1,tre[q].rs[0]=a;
        COST=tre[a].d;
        tre[a].f=f,tre[a].x=x;
        if(tre[a].d==1)rroot=a;
        splay(a,0);
    }
    else if(x<tre[a].x)insrt(tre[a].s[0],a,x);
    else insrt(tre[a].s[1],a,x);
}

void rside(int sd)
{
    int a=root;
    while(tre[a].s[sd])psd(a),a=tre[a].s[sd];psd(a);
    COST=tre[a].d;
    int b=(sd?suf(root,tre[tre[a].rf].x):pre(root,tre[tre[a].rf].x));
    int sa=tre[a].rs[!sd],fa=tre[a].rf;
    if(!fa)return;
    tre[fa].rs[sd]=sa;
    if(sa)tre[sa].rf=fa;
    tre[a].rs[!sd]=rroot;
    tre[rroot].rf=a;
    tre[a].rf=0;
    rroot=a;
    splay(b,0);
    int c=tre[b].s[!sd];
    if(c)tre[c].d++,tre[c].l++;
    tre[a].d=1;
    splay(suf(root,tre[sa].x-1),0);
}

void del(int sd)
{
    rside(sd);
    int a=rroot;
    splay(a,0);
    int c=tre[a].s[!sd],d=tre[a].rs[!sd];
    if(c)tre[c].d--,tre[c].l--;
    tre[c].f=0;
    tre[d].rf=0;
    rroot=d;
    root=c;
}

inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x;
}

int main()
{
    int o,a;
    n=read();
    for(int i=1;i<=n;i++)
    {
        o=read();
        if(o==1)a=read(),insrt(root,0,a),printf("%d\n",COST);
        else if(o==2)rside(0),printf("%d\n",COST);
        else if(o==3)rside(1),printf("%d\n",COST);
        else if(o==4)del(0),printf("%d\n",COST);
        else del(1),printf("%d\n",COST);
    }
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *