[bzoj3595]-[SCOI2014]方伯伯的Oj

题目（BZOJ）
题目（洛谷）
 
大致思想就是把没有操作过的区间当作点插进splay中，另开一个map来存每个点的编号对应在splay上的点，就完成了。

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
    if(ck)e=-e;
}
const int N=300050;
int n,Q,ans;
map <int,int> mp;
int mn,mx;
int ch[N][2],fa[N],siz[N],L[N],R[N],id[N],rt,sz;
inline int get(int x){return ch[fa[x]][1]==x;}
inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+R[x]-L[x]+1;}
inline void roll(int x){
    int y=fa[x],z=fa[y],l=get(x),r=l^1;
    if(y==rt)rt=x;else ch[z][get(y)]=x;
    fa[x]=z;fa[y]=x;
    ch[y][l]=ch[x][r];ch[x][r]=y;
    if(ch[y][l])fa[ch[y][l]]=y;
    pushup(y);pushup(x);
}
inline void splay(int x,int k){
    while(fa[x]!=k){
        if(fa[fa[x]]!=k){
            get(x)==get(fa[x])?roll(fa[x]):roll(x);
        }
        roll(x);
    }
}
inline void insert(int &x,int l,int r,int last,int idx){
    if(l>r)return;
    if(!x){
        x=++sz;L[x]=l,R[x]=r;siz[x]=r-l+1;
        fa[x]=last;id[x]=idx;return;
    }
    if(r<L[x])insert(ch[x][0],l,r,x,idx);
    else insert(ch[x][1],l,r,x,idx);
    pushup(x);
}
int find_pos(int x,int v){
    if(L[x]<=v&&v<=R[x])return x;
    else if(L[x]>v)return find_pos(ch[x][0],v);
    else return find_pos(ch[x][1],v);
}
int find_rank(int x,int rank){
    int l=ch[x][0],r=ch[x][1];
    if(rank>siz[l]&&siz[r]+rank<=siz[x]){
        if(L[x]==R[x])return id[x];
        else return L[x]+rank-siz[l]-1;
    }
    else if(rank<=siz[l])return find_rank(l,rank);
    else return find_rank(r,rank-(siz[x]-siz[r]));
}
inline void del(int x,int v){
    if(!ch[x][1]){rt=ch[x][0];fa[ch[x][0]]=0;}
    else{
        int y=ch[x][1];while(ch[y][0])y=ch[y][0];
        splay(y,x);rt=y;fa[y]=0;
        if(ch[x][0])ch[y][0]=ch[x][0],fa[ch[x][0]]=y;
        pushup(y);
    }
    insert(rt,L[x],v-1,0,L[x]);splay(sz,0);
    insert(rt,v+1,R[x],0,v+1);splay(sz,0);
}
inline void change(int x,int v,int idx){
    if(L[x]==R[x])id[x]=idx;
    else{del(x,v);insert(rt,v,v,0,idx);splay(sz,0);}
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("input0.in","r",stdin);
    freopen("myans.out","w",stdout);
#endif
    read(n),read(Q);mx=n,mn=0;
    insert(rt,1,n,0,1);
    while(Q--){
        int opt,x,y;read(opt);
        switch(opt){
            case 1:{
                read(x),read(y);x-=ans;y-=ans;
                int v=mp[x];if(!v)v=x;
                int now=find_pos(rt,v);splay(now,0);
                ans=siz[ch[now][0]]+v-L[now]+1;
                change(now,v,y);mp[x]=0;mp[y]=v;
                break;
            }
            case 4:{
            	read(x);x-=ans;
            	ans=find_rank(rt,x);
                break;
            }
            default:{
                read(x);x-=ans;
                int v=mp[x];if(!v)v=x;
                int now=find_pos(rt,v);splay(now,0);
                ans=siz[ch[now][0]]+v-L[now]+1;
                del(now,v);
                v=mp[x]=(opt==2?--mn:++mx);
                insert(rt,v,v,0,x);splay(sz,0);
                break;
            }
        }
        printf(
    }
    return 0;
}