平衡树蒟蒻，敲了半天。

其实思路很简单，就是把许多个人合并成一个区间。必要的时候再拆开。（是不是和这个题的动态开点线段树有异曲同工之妙？）

每次操作最多多出来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
     
      #define reg register int#define il inlineusing 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
      
       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