BZOJ4825 单旋

分析：一道水题，去年考场发现了特点但是不会splay维护挂了，然后现在我写了个treap。

画一画图就可以解决这道题了，自己试一下。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

int m,xxx;

namespace Treap{

    struct spaly{int son[],fa;}t[maxn];

    int sz[maxn],ch[maxn][],num,SpalyRoot,Prs[maxn];

    int key[maxn],lazy[maxn],dep[maxn],data[maxn],root;

    void push_down(int now){

        dep[now] += lazy[now];

        lazy[ch[now][]] += lazy[now]; lazy[ch[now][]] += lazy[now];

        lazy[now] = ;

    }

    int merge(int root1,int root2){

        if(!root1) return root2; if(!root2) return root1;

        if(lazy[root1]) push_down(root1); if(lazy[root2]) push_down(root2);

        if(key[root1] <= key[root2]){

            ch[root1][] = merge(ch[root1][],root2);

            Prs[ch[root1][]] = root1;

            sz[root1] = sz[ch[root1][]] + sz[ch[root1][]] + ;

            return root1;

        }else{

            ch[root2][] = merge(root1,ch[root2][]);

            Prs[ch[root2][]] = root2;

            sz[root2] = sz[ch[root2][]] + sz[ch[root2][]] + ;

            return root2;

        }

    }

    pair<int,int> split(int Node,int Len){

        if(Len == ) return make_pair(,Node);

        if(Node == ) return make_pair(,);

        if(lazy[Node]) push_down(Node);

        if(sz[ch[Node][]] >= Len){

            pair<int,int> Ans = split(ch[Node][],Len);

            ch[Node][] = Ans.second; Prs[Ans.second] = Node;

            Ans.second = Node; Prs[Ans.first] = ;

            sz[Node] = sz[ch[Node][]] + sz[ch[Node][]] + ;

            return Ans;

        }else{

            pair<int,int> Ans = split(ch[Node][],Len-sz[ch[Node][]]-);

            ch[Node][] = Ans.first; Prs[Ans.first] = Node;

            Ans.first = Node; Prs[Ans.second] = ;

            sz[Node] = sz[ch[Node][]] + sz[ch[Node][]] + ;

            return Ans;

        }

    }

    int get_rank(int Node,int Val){

        if(Node == ) return ;

        if(data[Node] > Val) return get_rank(ch[Node][],Val);

        else return sz[ch[Node][]]++get_rank(ch[Node][],Val);

    }

    int get_Kth(int Node){

        stack<int> sta; int pts = Node;

        while(pts){sta.push(pts),pts = Prs[pts];}

        int Th = ;

        while(!sta.empty()){

            int dat = sta.top();sta.pop();

            if(lazy[dat]) push_down(dat);

            if(!sta.empty()&&ch[dat][] == sta.top()){

                Th += sz[ch[dat][]] + ;

            }

        }

        Th += sz[ch[Node][]] + ;

        return Th;

    }

}

namespace operation{

    using namespace Treap;

    int Insert(int Val){

        if(root == ){

            root++;sz[root]=;key[root]=rand();data[root]=Val;dep[root]=;

            num++;SpalyRoot++;return dep[root];

        }

        num++;sz[num] = ;key[num] = rand();data[num] = Val;

        int rk = get_rank(root,Val);

        pair<int,int> nowp = split(root,rk);

        int rt = nowp.first,lt = nowp.second;

        while(ch[rt][]) {if(lazy[rt])push_down(rt); rt = ch[rt][];}

        while(ch[lt][]) {if(lazy[lt])push_down(lt); lt = ch[lt][];}

        if(lazy[rt]&&rt) push_down(rt); if(lazy[lt]&&lt) push_down(lt);

        if(!t[rt].son[] && rt != ){

            t[rt].son[] = num;t[num].fa = rt;dep[num] = dep[rt]+;

        }else{

            t[lt].son[] = num;t[num].fa = lt;dep[num] = dep[lt]+;

        }

        root = merge(merge(nowp.first,num),nowp.second);

        return dep[num];

    }

    int Spaly(int Kind){ // 0 min,1 max

        int nowp = root;

        while(ch[nowp][Kind]){

            if(lazy[nowp])push_down(nowp); nowp=ch[nowp][Kind];

        }

        if(nowp == SpalyRoot){return ;}

        int Son = t[nowp].son[Kind^],Father = t[nowp].fa;

        t[nowp].son[Kind^] = SpalyRoot; t[SpalyRoot].fa = nowp;

        SpalyRoot = nowp;t[nowp].fa = ;int finalans;

        int Len = get_Kth(Father);

        t[Father].son[Kind] = Son; t[Son].fa = Father;

        if(Kind == ){

            pair<int,int> Ans = split(root,Len-);

            pair<int,int> Cut = split(Ans.first,);

            lazy[Ans.second]++;

            if(lazy[Cut.first]) push_down(Cut.first);

            finalans = dep[nowp]; dep[Cut.first] = ;

            root = merge(merge(Cut.first,Cut.second),Ans.second);

        }else{

            pair<int,int> Ans = split(root,Len);

            pair<int,int> Cut = split(Ans.second,sz[Ans.second]-);

            lazy[Ans.first]++;

            if(lazy[Cut.second]) push_down(Cut.second);

            finalans = dep[nowp];dep[Cut.second] = ;

            root = merge(Ans.first,merge(Cut.first,Cut.second));

        }

        return finalans;

    }

    int Erase(int Kind){//0 min 1 max

        int finalans = Spaly(Kind);

        int nowp = root;

        while(ch[nowp][Kind]){

            if(lazy[nowp])push_down(nowp); nowp=ch[nowp][Kind];

        }

        SpalyRoot = t[nowp].son[Kind^];

        t[SpalyRoot].fa = ;t[nowp].son[Kind^] = ;

        pair<int,int> Les = split(root,get_Kth(nowp));

        pair<int,int> Spt = split(Les.first,get_Kth(nowp)-);

        root = merge(Spt.first,Les.second);

        if(root != ) lazy[root]--;

        return finalans;

    }

}

void work(){

    for(int i=;i<=m;i++){xxx=i;

        int opt,x; scanf("%d",&opt);

        if(opt ==  || opt == ) printf("%d\n",operation::Spaly(opt%));

        else if(opt ==  || opt == ) printf("%d\n",operation::Erase(opt%));

        else {scanf("%d",&x);printf("%d\n",operation::Insert(x));}

    }

}

int main(){

    srand();

    scanf("%d",&m);

    work();

    return ;

}