突然不会写学习笔记了...

反正是给自己看的

那就想到哪写到哪吧

思想

不基于旋转而基于暴力重构的平衡树

采用懒惰删除法 每次删除只打标记，在重构时统一删除

如果某个点的子树过于不平衡或删除了过多的元素 那就需要进行重构

重构时暴力dfs整棵子树，碰见打了删除标记的节点就扔进内存池，否则按照中序遍历存下来，然后递归建满二叉树即可。

代码长这样：

void dfs(int &len,int x){    if(!x) return;    dfs(len,ls);    if(!del[x]) cz[++len]=x;    else dp[++dc]=x;    dfs(len,rs);}int build(int l,int r){    if(l>r) return 0;    int mid=l+r>>1;    int x=cz[mid];sze[x]=1;cnt[x]=1;ls=rs=0;del[x]=0;    if(l==r) return x;    ls=build(l,mid-1),rs=build(mid+1,r);    if(ls) fa[ls]=x;    if(rs) fa[rs]=x;    pushup(x); return x;}void pia(int x){    int f=fa[x],len=0;    dfs(len,x);    int t=build(1,len);    if(root==x) root=t;    else ch[f][ch[f][1]==x]=t,fa[t]=f;}

一定要注意及时更新信息

普通平衡树的代码：

#pragma GCC optimize(2)#include
    
     using std::min;using std::max;using std::swap;using std::vector;typedef double db;typedef long long ll;#define pb(A) push_back(A)#define pii std::pair
     
      #define all(A) A.begin(),A.end()#define mp(A,B) std::make_pair(A,B)const int N=1e6+5;const db alph=0.75;#define ls ch[x][0]#define rs ch[x][1]int n,tot,dp[N],dc,cz[N];int sze[N],ch[N][2],cnt[N];int val[N],root,del[N],fa[N];int newnode(){    int t=dc?dp[dc--]:++tot;    fa[t]=cnt[t]=sze[t]=val[t]=ch[t][0]=ch[t][1]=del[t]=0;    return t;}bool chk(int x){    return alph*sze[x]<=max(sze[ls],sze[rs]) or alph*cnt[x]>sze[x];}void dfs(int &len,int x){    if(!x) return;    dfs(len,ls);    if(!del[x]) cz[++len]=x;    else dp[++dc]=x;    dfs(len,rs);}void pushup(int x){    cnt[x]=cnt[ls]+cnt[rs]+1;    sze[x]=sze[ls]+sze[rs]+!del[x];}int build(int l,int r){    if(l>r) return 0;    int mid=l+r>>1;    int x=cz[mid];sze[x]=1;cnt[x]=1;ls=rs=0;del[x]=0;    if(l==r) return x;    ls=build(l,mid-1),rs=build(mid+1,r);    if(ls) fa[ls]=x;    if(rs) fa[rs]=x;    pushup(x); return x;}void pia(int x){    int f=fa[x],len=0;    dfs(len,x);    int t=build(1,len);    if(root==x) root=t;    else ch[f][ch[f][1]==x]=t,fa[t]=f;}int ins(int x,int v,int f,int &flag){    if(!x){        x=newnode();        cnt[x]=sze[x]=1,val[x]=v,fa[x]=f;        return x;    } int d=val[x]
      
       =rk) erase(ls,rk,flag);    else erase(rs,rk-sze[ls]-!del[x],flag);    if(chk(x)) flag=x;}int kth(int x,int k){    if(!del[x]){        if(sze[ls]==k-1) return val[x];        if(sze[ls]>=k) return kth(ls,k);        return kth(rs,k-sze[ls]-1);    } else{        if(sze[ls]>=k) return kth(ls,k);        else return kth(rs,k-sze[ls]);    }}int find(int x,int k){    if(!x) return 0;    if(val[x]>=k) return find(ls,k);    else return find(rs,k)+sze[ls]+!del[x];}int getint(){    int X=0,w=0;char ch=getchar();    while(!isdigit(ch))w|=ch=='-',ch=getchar();    while( isdigit(ch))X=X*10+ch-48,ch=getchar();    if(w) return -X;return X;}signed main(){    n=getint();    while(n--){        int opt=getint(),x=getint();        if(opt==1 or opt==2){            int flag=0;            if(opt==1) root=ins(root,x,0,flag);            else erase(root,find(root,x)+1,flag);            if(flag) pia(flag);        }        if(opt==3) printf("%d\n",find(root,x)+1);        if(opt==4) printf("%d\n",kth(root,x));        if(opt==5) printf("%d\n",kth(root,find(root,x)));        if(opt==6) printf("%d\n",kth(root,find(root,x+1)+1));    } return 0;}
      
     
    

突然想到了一种不用记录fa的方法哈哈哈哈哈！！！

我们需要记录fa的本质原因是因为在重构的时候要更改fa的ch数组

既然这样我们传参的时候传一个pair包括x和fa[x]不就好了！

哈哈哈哈哈我真是个小机灵鬼