平衡树蒟蒻，敲了半天。
其实思路很简单，就是把许多个人合并成一个区间。必要的时候再拆开。（是不是和这个题的动态开点线段树有异曲同工之妙？）
每次操作最多多出来6个点。
理论上时间复杂度是nlogn，空间复杂度实际远远小于上界，其实4*n即可。
出错点：
1.pushup把哨兵sz变成了1：pushup要特判x！=0（比较保险）
2.fa和son的边一定要成对一起添加！！t[t[y].ch[0]=t[x].ch[0]].fa=y 压行的话不容易漏。
3.对于一列的情况，可能删除之后整个树空了。但是如果直接找的话，因为哨兵0有奇奇怪怪的左右儿子和father，所以，一路上会把0的sz变成1，并且访问到奇奇怪怪的点23333
那就特判如果没有根的话，那就直接建立即可。
代码：
#include<bits/stdc++.h> #define reg register int #define il inline using namespace std; typedef long long ll; const int N=300000+5; struct node{ int ch[2]; int sz; int L,R; int fa; ll val; }t[N*6]; int tot; void rd(int &x){ char ch;x=0; while(!isdigit(ch=getchar())); for(x=ch^'0';isdigit(ch=getchar());x=x*10+(ch^'0')); } int rt[N]; int now; int n,m,q; void pushup(int x){ if(x) t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+t[x].R-t[x].L+1; } void rotate(int x){ int y=t[x].fa,d=(t[y].ch[1]==x); t[t[y].ch[d]=t[x].ch[!d]].fa=y; t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x; t[t[x].ch[!d]=y].fa=x; pushup(y); } void splay(int x,int f){ while(t[x].fa!=f){ int y=t[x].fa,z=t[y].fa; if(z!=f){ rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x); } rotate(x); } pushup(x); if(f==0) rt[now]=x; } ll get(int pos){ if(now==n+1){ return (ll)pos*m; } return (ll)(now-1)*m+pos; } void ins(int x,ll c){ if(x==0){ ++tot; t[tot].fa=0; t[tot].val=c; t[tot].L=t[tot].R=0; pushup(tot); rt[now]=tot; } else{ while(t[x].ch[1]) t[x].sz++,x=t[x].ch[1]; ++tot; t[x].ch[1]=tot; t[tot].fa=x; t[tot].L=t[tot].R=0;t[tot].val=c; t[tot].sz=1; pushup(x); splay(tot,0); int tmp=rt[now]; } } ll query(int x,int k){//and dele int d=k-t[t[x].ch[0]].sz; if(d<=0) return query(t[x].ch[0],k); else if(t[x].R-t[x].L+1<d) return query(t[x].ch[1],d-(t[x].R-t[x].L+1)); else{//find position ll ret=0; if(t[x].R>t[x].L){ if(d>1){ ++tot; t[tot].L=t[x].L;t[tot].R=t[x].L+d-2; t[t[tot].ch[0]=t[x].ch[0]].fa=tot; t[t[x].ch[0]=tot].fa=x; pushup(tot); } if(d<t[x].R-t[x].L+1){ ++tot; t[tot].L=t[x].L+d;t[tot].R=t[x].R; t[t[tot].ch[1]=t[x].ch[1]].fa=tot; t[t[x].ch[1]=tot].fa=x; pushup(tot); } t[x].val=get(t[x].L+d-1); t[x].L=t[x].R=0; }else if(t[x].R){ t[x].val=get(t[x].R); t[x].L=t[x].R=0; } pushup(x); ret=t[x].val; splay(x,0); int son=t[x].ch[1]; if(!son){ t[rt[now]=t[x].ch[0]].fa=0; pushup(rt[now]); } else{ while(t[son].ch[0]) son=t[son].ch[0]; splay(son,rt[now]); t[t[son].ch[0]=t[x].ch[0]].fa=son; t[son].fa=0; pushup(son); rt[now]=son; } return ret; } } int main(){ rd(n);rd(m);rd(q); int x,y; for(reg i=1;i<=n;++i){ rt[i]=++tot; t[tot].L=1,t[tot].R=m-1; t[tot].sz=m-1; t[tot].fa=0; } rt[n+1]=++tot; t[tot].L=1,t[tot].R=n; t[tot].sz=n; while(q--){ rd(x);rd(y); ll id=0; if(y==m) now=n+1,id=query(rt[now],x); else now=x,id=query(rt[now],y); printf("%lld ",id); now=n+1; ins(rt[now],id); if(y!=m){ now=n+1; id=query(rt[now],x); now=x; ins(rt[now],id); } } return 0; }