单旋

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

——-鲁迅

题意：

​ 如果 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;
}