BZOJ 4825 [Hnoi2017]單旋

splay

觀察這種spaly的性質。插入一個點，這個點的深度就是它的前驅後繼中深度較大的那個+1。單旋最小值，則最小值的右子樹裡的點深度不變，自己深度變為1，其他點深度+1，單旋最大值同理。删除則在這個基礎上讓全部深度-1。

這個是在平衡樹上的子樹維護，也就是一個區間維護，離線上線段樹即可。然而我還是帶着敬意地寫了一個splay……

#include<set>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
namespace runzhe2000
{
    typedef long long ll;
    const int INF = <<;
    int m; ll ans;

    struct node
    {
        node *ch[], *fa;
        int key, dep, mi, tag;
    }mem[N], *tot, *null, *root;
    void init()
    {
        root = null = tot = mem;
        null->ch[] = null->ch[] = null->fa = null;
        null->dep = null->mi = INF, null->tag = ;
    }
    int type(node *x){return x->fa->ch[1]==x;}
    node* newnode(int key, int dep){node *p = ++tot; *p = *null; p->key = key, p->dep = p->mi = dep; return p;}
    void pushup(node *x){x->mi = min(x->dep, min(x->ch[]->mi, x->ch[]->mi));}
    void pushdown(node *x)
    {
        if(!x->tag) return;
        if(x->ch[] != null) x->ch[]->tag += x->tag,x->ch[]->dep += x->tag,x->ch[]->mi  += x->tag; 
        if(x->ch[] != null) x->ch[]->tag += x->tag,x->ch[]->dep += x->tag,x->ch[]->mi  += x->tag;
        x->tag = ;
    }
    void rotate(node *x)
    {
        node *f = x->fa; int d = type(x);
        (x->fa = f->fa) != null ? x->fa->ch[type(f)] = x : 0;
        (f->ch[d] = x->ch[!d]) != null ? f->ch[d]->fa = f : ;
        x->ch[!d] = f, f->fa = x, pushup(f);
    }
    void update(node *x){if(x==null)return;update(x->fa);pushdown(x);}
    void splay(node *x)
    {
        update(x);
        for(;x->fa!=null;)
        {
            if(x->fa->fa == null) rotate(x);
            else if(type(x)==type(x->fa))rotate(x->fa),rotate(x);
            else rotate(x),rotate(x);
        }       
        pushup(root = x);
    }
    void insert(node *x, node *f, node *p, int d, node *la, node *ra)
    {
        if(root == null) 
        {
            root = p; 
            p->dep = p->mi = ;
            return;
        }
        if(x == null)
        {
            p->fa = f, f->ch[d] = p; 
            p->dep = p->mi = max(la->dep==INF?:la->dep, ra->dep==INF?:ra->dep) + ;
            return;
        }
        pushdown(x); if(p->key < x->key) insert(x->ch[], x, p, , la, x);
        else insert(x->ch[], x, p, , x, ra); pushup(x);
    }
    node* select(node *p, int type)
    {
        pushdown(p); if(type) return p->ch[1]!=null ? select(p->ch[1], 1) : p;
        else return p->ch[]!=null ? select(p->ch[], ) : p;
    }
    node* find(node *x, int d, int type) // < d
    {
        pushdown(x);
        if(type)
        {
            if(x->ch[]->mi < d) return find(x->ch[], d, );
            else if(x->dep < d) return x;
            else return find(x->ch[], d, );
        }
        else
        {
            if(x->ch[]->mi < d) return find(x->ch[], d, );
            else if(x->dep < d) return x;
            else return find(x->ch[], d, );
        }
    }

    void main()
    {
        init(); scanf("%d",&m);
        for(int _ = , c; _ <= m; _++)
        {
            scanf("%d",&c);
            if(c == )
            {
                int key; scanf("%d",&key); node *p = newnode(key,);
                insert(root, null, p, , null, null); splay(p); ans = p->dep;
            }
            else if(c ==  || c == )
            {
                node *p = select(root, ); ans = p->dep;
                if(p->dep != )
                {
                    node *q = find(root, p->dep, );
                    splay(q);
                    if(q->ch[] != null) q->ch[]->dep ++, q->ch[]->mi++, q->ch[]->tag++;
                    q->dep++; pushup(q);
                    splay(p); p->dep = ; pushup(p);
                }
                if(c == )
                {
                    splay(p); root = p->ch[]; root->fa = null;
                    if(root != null) root->dep--, root->mi--, root->tag--;
                }
            }
            else if(c ==  || c == )
            {
                node *p = select(root, ); ans = p->dep;
                if(p->dep != )
                {   
                    node *q = find(root, p->dep, );
                    splay(q); 
                    if(q->ch[] != null) q->ch[]->dep ++, q->ch[]->mi++, q->ch[]->tag++;
                    q->dep++; pushup(q);
                    splay(p); p->dep = ; pushup(p);
                }
                if(c == )
                {
                    splay(p); root = p->ch[]; root->fa = null;
                    if(root != null) root->dep--, root->mi--, root->tag--;
                }
            }
            printf("%lld\n",ans);
        }
    }
}
int main()
{
    runzhe2000::main();
}