题目描述：https://www.luogu.org/problemnew/show/P3285
解析：首先发现n的范围很大，但m的范围很小，所以被操作的点最多只有1e5个点，于是想到用一个点表示一段区间，要用的时候再拆开。怎么实现呢？想到用一颗平衡树来维护排名，每一个节点记录在原序列中的一段区间的左端点和右端点，用map来维护一段区间的右端点所在节点的编号，这样做就可以快速找到一个值所在splay中的节点编号。这样1操作就可以很顺利的解决了，记得拆开点之后要更新每个节点的L和R以及与m的更新。对于2操作，可先将该节点splay至根，再将根的左儿子直接连向该点的后继，最后将后继的左儿子转到根，这样既能更新子树的大小又能保证时间复杂度。3操作与2同理。对于4操作，直接查k大就可以了。
细节：好像没什么细节，不要写挂就好。
附上代码：
#include<cstdio> #include<iostream> #include<map> #include<algorithm> using namespace std; const int MAXM=1e5+5; int n,m; struct Node{ int size,l,r,fa,son[2]; }node[MAXM<<1]; map<int,int> mp; int root; int ndnum=0; int ans=0; inline int read(){ int ret=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-f;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) ret=ret*10+ch-‘0‘,ch=getchar(); return ret*f; } int new_node(int l,int r){ int x=++ndnum; node[x].fa=node[x].son[0]=node[x].son[1]=0; node[x].l=l;node[x].r=r; node[x].size=node[x].r-node[x].l+1; return x; } void update(int x){ int lson=node[x].son[0],rson=node[x].son[1]; node[x].size=node[lson].size+node[rson].size+node[x].r-node[x].l+1; } void split(int pos,int x){ int lson=0,rson=0; if(node[pos].l==node[pos].r) return; mp[x]=pos; if(node[pos].l!=x){ lson=mp[x-1]=new_node(node[pos].l,x-1); node[lson].fa=pos; node[lson].son[0]=node[pos].son[0]; node[node[lson].son[0]].fa=lson; node[pos].son[0]=lson; node[pos].size=1; } if(node[pos].r!=x){ rson=mp[node[pos].r]=new_node(x+1,node[pos].r); node[rson].fa=pos; node[rson].son[1]=node[pos].son[1]; node[node[rson].son[1]].fa=rson; node[pos].son[1]=rson; node[pos].size=1; } node[pos].l=node[pos].r=x; if(lson) update(lson); if(rson) update(rson); update(pos); } int check(int x){ return x==node[node[x].fa].son[1]; } void rotate(int x){ int y=node[x].fa,z=node[y].fa,d=check(x),xx=node[x].son[d^1]; node[y].son[d]=xx;node[xx].fa=y; node[z].son[check(y)]=x;node[x].fa=z; node[x].son[d^1]=y;node[y].fa=x; update(y);update(x); } void splay(int x,int to=0){ while(node[x].fa!=to){ int y=node[x].fa,z=node[y].fa; if(z!=to){ if(check(x)==check(y)) rotate(y); else rotate(x); } rotate(x); } if(!to) root=x; } int rank(int x){ splay(x); return node[node[root].son[0]].size+1; } void merge(int x){ splay(x); if(!node[x].son[0]) return; else if(!node[x].son[1]) {swap(node[x].son[0],node[x].son[1]);return;} else{ int cur=node[x].son[1]; while(node[cur].son[0]) cur=node[cur].son[0]; int lson=node[x].son[0]; node[lson].fa=cur; node[cur].son[0]=lson; node[x].son[0]=0; update(node[x].son[1]);update(x); splay(lson); } } void fmerge(int x){ splay(x); if(!node[x].son[1]) return; else if(!node[x].son[0]) {swap(node[x].son[0],node[x].son[1]);return;} else{ int cur=node[x].son[0]; while(node[cur].son[1]) cur=node[cur].son[1]; int rson=node[x].son[1]; node[rson].fa=cur; node[cur].son[1]=rson; node[x].son[1]=0; update(node[x].son[0]);update(x); splay(rson); } } int find(int kth){ int cur=root; while(1){ int lson=node[cur].son[0],rson=node[cur].son[1]; if(kth<=node[lson].size) cur=lson; else if(kth>node[lson].size+node[cur].r-node[cur].l+1){ kth-=node[lson].size+node[cur].r-node[cur].l+1; cur=rson; } else{ kth-=node[lson].size; return node[cur].l+kth-1; } } } int main(){ n=read();m=read(); mp[n]=root=new_node(1,n); for(int i=1;i<=m;i++){ int opt=read(); if(opt==1){ int x=read(),y=read(); x-=ans;y-=ans; int pos=(*mp.lower_bound(x)).second; split(pos,x); ans=rank(pos); node[pos].l=node[pos].r=y; mp[y]=pos; printf("%d\n",ans); } if(opt==2){ int x=read(); x-=ans; int pos=(*mp.lower_bound(x)).second; split(pos,x); ans=rank(pos); merge(pos); printf("%d\n",ans); } if(opt==3){ int x=read(); x-=ans; int pos=(*mp.lower_bound(x)).second; split(pos,x); ans=rank(pos); fmerge(pos); printf("%d\n",ans); } if(opt==4){ int x=read(); x-=ans; ans=find(x); printf("%d\n",ans); } } return 0; }
原文：https://www.cnblogs.com/JoshDun/p/11232617.html
