终于用自己的方法水过去了。
本地测慢的一组要三四秒，一共要十几秒，BZOJ貌似一共只让跑6s，于是就还T着的。
一开始没看n<=1e8，想的直接splay+map（splay维护名次，map维护对应标号的节点所在位置）
然后写完看到n的范围 就傻了= =
百度了一下 splay里面的点要包含一段区间
想了半天 自己yy了一个做法：
一开始就一个点：[1,n+2]（虚拟节点什么的蛋疼死了，一会+1，一会-1）
于是需要[l,r]中的p点时，就拆成[l,p-1][p,p][p+1,r]，可是这样会不会影响树的形状？
分析一下，表示区间的点是不会有儿子的，所以我们可以很自然的把这样的点当成普通点看待。
然后又有一个问题，如何找到这个点在哪个区间里？
一开始想的建两个splay，另一个splay就是用来干这个的，觉得太麻烦就一直没写。
最后YY出用set来维护，用set<node(l,r,id)>来维护每个区间，每产生一个区间，就把他扔到set里，然后按r排序
不难发现，对于x，>=x的第一个r所在的区间一定包含它。然后找到split即可……
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<iostream> #include<map> #include<set> using namespace std; const int Maxn=400000+10; inline int getint(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c)&&c!='-';c=getchar()); if(c=='-')f=0; for(;isdigit(c);c=getchar())x=x*10+c-'0'; return f?x:-x; } inline void getint(int&x){x=getint();} struct node{ int l,r,id; inline bool operator<(const node&rhs)const{return r<rhs.r;} node(int l,int r,int id):l(l),r(r),id(id){} }; int n,m,a; map<int,int>pos; set<node> Set; typedef set<node>::iterator it; typedef int pnode; struct Splay{ int lp[Maxn],rp[Maxn],p[Maxn],l[Maxn],r[Maxn],sz[Maxn],v[Maxn],cnt,tot,root; inline void update(int x){ if(lp[x]==rp[x])sz[x]=sz[l[x]]+sz[r[x]]+1; else sz[x]=rp[x]-lp[x]+1; } inline void split(int x,int mid){// x is a node in Splay Tree and mid is a pointer but not a value Set.erase(node(lp[x],rp[x],x)); int L=0,R=0; if(lp[x]!=mid){ L=++tot; l[x]=L; p[L]=x; lp[L]=lp[x]; rp[L]=mid-1; if(lp[L]==rp[L]){ v[L]=lp[x]-1; if(v[L]==n+1)v[L]=0; if(v[L])pos[v[L]]=L; } else Set.insert(node(lp[L],rp[L],L)); } if(rp[x]!=mid){ R=++tot; r[x]=R; p[R]=x; lp[R]=mid+1; rp[R]=rp[x]; if(lp[R]==rp[R]){ v[R]=rp[x]-1; if(v[R]==n+1)v[R]=0; if(v[R])pos[v[R]]=R; } else Set.insert(node(lp[R],rp[R],R)); } v[x]=mid-1; if(v[x]==n+1)v[x]=0; if(v[x])pos[v[x]]=x; rp[x]=lp[x]=mid; if(L)update(L); if(R)update(R); update(x); } inline int find(int x){// x is stand for val int t=pos[x]; if(t)return t; it p=Set.lower_bound(node(0,x+1,0)); t=p->id; split(t,x+1); return t; } inline void zig(int x){ int y=p[x],z=p[y],w=r[x]; l[y]=w;r[x]=y; if(l[z]==y)l[z]=x; if(r[z]==y)r[z]=x; p[x]=z;p[y]=x;if(w)p[w]=y; update(y);update(x); } inline void zag(int x){ int y=p[x],z=p[y],w=l[x]; r[y]=w;l[x]=y; if(l[z]==y)l[z]=x; if(r[z]==y)r[z]=x; p[x]=z;p[y]=x;if(w)p[w]=y; update(y);update(x); } inline void rotate(int x){ if(l[p[x]]==x)zig(x);else zag(x); } inline void splay(int x,int FA){ for(;p[x]!=FA;){ int y=p[x],z=p[y]; if(z!=FA){ if( (l[y]==x)^(l[z]==y) )rotate(x);else rotate(y); } rotate(x); } if(!FA)root=x; } inline void init(){ cnt=tot=sz[0]=0; root=++tot=1; lp[root]=1,rp[root]=n+2; Set.insert(node(1,n+2,root)); update(root); } int kth(int o,int k){ if(rp[o]!=lp[o]){ split(o,lp[o]+k-1); return o; } int s=sz[l[o]]; if(s+1==k)return o; if(s+1<k)return kth(r[o],k-s-1); return kth(l[o],k); } inline int deal(){ if(m==2) m=2; int x,y,opt; getint(opt); if(opt==1){ getint(x),getint(y); x-=a,y-=a; int o=find(x); v[o]=y; pos[x]=0; pos[y]=o; splay(o,0); return a=sz[l[o]]; } else if(opt==2||opt==3){ getint(x);x-=a; x=find(x); splay(x,0); int rk=sz[l[x]]; if(rk==n&&opt==3)return a=rk; if(rk==1&&opt==2)return a=rk; int lt=kth(root,rk-1 +1),rt=kth(root,rk+1 +1);//for the static 1 splay(lt,0); splay(rt,lt); l[rt]=0; update(rt); update(lt); int fst,snd; if(opt==2)fst=kth(root,1),snd=kth(root,2); else fst=kth(root,n),snd=kth(root,n+1);//for 1 has been killed splay(fst,0); splay(snd,fst); l[snd]=x; p[x]=snd; update(snd); update(fst); return a=rk; } else { getint(x);x-=a; return a=v[kth(root,x+1)]; } } }sp; int main(){ freopen("onlinejudge.in","r",stdin); freopen("onlinejudge.out","w",stdout); scanf("%d%d",&n,&m); sp.init(); for(;m--;)printf("%d\n",sp.deal()); return 0; }