[Scoi2014]方伯伯的OJ（动态开点splay）

开始没看数据范围差点以为是这题了：https://www.cnblogs.com/hfctf0210/p/10911340.html

然后看到n<=1e8，怎么这么大？

所以这题需要用动态开点线段树或者动态开点splay，而我上面的那题写的树状数组，为了熟悉splay就用动态开点splay吧而且也不知道这题动态开点线段树怎么写。正常要开两棵splay，但是关于用户的一棵操作简单没有必要开，所以可以用map代替，为了方便lower_bound查询，map记录右端点。然后先要执行三个基本操作：1、查询第k大。2、查询k节点的rank。3、分裂节点，分裂就是直接开新节点即可。然后重点在于2,3操作，一种简便的方法就是将目标节点拆开并旋转到根，将左右子树合并，使其成为第一/倒一。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct node{int ch[2],sz,l,r,fa;}t[N<<2];
int n,m,root,cnt,ans;
map<int,int>mp;
int newnode(int l,int r)
{
    int k=++cnt;
    t[k].ch[0]=t[k].ch[1]=0;
    t[k].l=l,t[k].r=r;
    t[k].sz=t[k].r-t[k].l+1;
    return k;
}
void pushup(int k){t[k].sz=t[t[k].ch[0]].sz+t[t[k].ch[1]].sz+t[k].r-t[k].l+1;}
int dir(int k){return t[t[k].fa].ch[1]==k;}
void rotate(int x)
{
    int y=t[x].fa,z=t[y].fa,d1=dir(x),d2=dir(y);
    t[y].ch[d1]=t[x].ch[d1^1];
    t[t[x].ch[d1^1]].fa=y;
    t[z].ch[d2]=x;
    t[x].fa=z;
    t[y].fa=x;
    t[x].ch[d1^1]=y;
    pushup(y),pushup(x);
}
void splay(int x,int goal)
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa,z=t[y].fa,d1=dir(x),d2=dir(y);
        if(z!=goal){if(d1==d2)rotate(y);else rotate(x);}
        rotate(x);
    }
    if(!goal)root=x;
}
int getkth(int rk)
{
    int k=root;
    while(1)
    {
        int son=t[k].ch[0];
        if(rk<=t[t[k].ch[0]].sz)k=t[k].ch[0];
        else if(rk>t[t[k].ch[0]].sz+t[k].r-t[k].l+1)
        rk-=t[t[k].ch[0]].sz+t[k].r-t[k].l+1,k=t[k].ch[1];
        else return t[k].l+rk-t[t[k].ch[0]].sz-1;
    }
}
int getrk(int k){splay(k,0);return t[t[k].ch[0]].sz+1;}
void split(int k,int id)
{
    if(t[k].l==t[k].r)return;
    int l=0,r=0;
    mp[id]=k;
    if(t[k].l!=id)
    {
        mp[id-1]=l=newnode(t[k].l,id-1);
        t[l].ch[0]=t[k].ch[0];
        t[t[l].ch[0]].fa=l;
        t[k].ch[0]=l;
        t[l].fa=k;
    }
    if(t[k].r!=id)
    {
        mp[t[k].r]=r=newnode(id+1,t[k].r);
        t[r].ch[1]=t[k].ch[1];
        t[t[r].ch[1]].fa=r;
        t[k].ch[1]=r;
        t[r].fa=k;
    }
    t[k].l=t[k].r=id;
    if(l)pushup(l);
    if(r)pushup(r);
    pushup(k);
}
void change(int k,int tp)
{
    splay(k,0);
    k=root;
    if(!t[k].ch[tp])return;
    if(!t[k].ch[tp^1])t[k].ch[tp^1]=t[k].ch[tp],t[k].ch[tp]=0;
    else{
        k=t[k].ch[tp^1];
        while(t[k].ch[tp])k=t[k].ch[tp];
        t[t[root].ch[tp]].fa=k;
        t[k].ch[tp]=t[root].ch[tp];
        t[root].ch[tp]=0;
        splay(t[k].ch[tp],0);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    root=mp[n]=newnode(1,n);
    while(m--)
    {
        int op,x,y,pos;scanf("%d%d",&op,&x),x-=ans;
        if(op==1)
        {
            scanf("%d",&y),y-=ans;
            pos=(*mp.lower_bound(x)).second;
            split(pos,x);
            printf("%d\n",ans=getrk(pos));
            t[pos].l=t[pos].r=y;
            mp[y]=pos;
        }
        else if(op==4)printf("%d\n",ans=getkth(x));
        else{
            int pos=(*mp.lower_bound(x)).second;
            split(pos,x);
            printf("%d\n",ans=getrk(pos));
            change(pos,op-2);
        }
    }
}