关于 WBLT

• Leafy Tree 在删除节点操作时可以不调用 maintain 函数吗？这个是否只影响常数？

• 对于这种类型的题，真的有必要用到双旋操作吗？

以下是本人代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int inf=INT_MAX;
const int Maxn=1.1e6+6;
int Q;
struct Leafy{
    int l,r;
    int sz,val;
}t[Maxn<<1];
int tot;

inline int newnode(int x){
    t[++tot]=(Leafy){0,0,1,x};
    return tot;
}
inline void update(int u){
    t[u].sz=t[t[u].l].sz+t[t[u].r].sz;
    t[u].val=t[t[u].r].val;
}

const double alpha=0.3;
#define ch(x,d) ((d)?t[x].r:t[x].l)

inline void rotate(int x, bool d) {  
    swap(t[x].l,t[x].r);
    swap(t[ch(x,d^1)].l,t[ch(x,d^1)].r);
    swap(ch(ch(x,d^1),d^1),ch(x,d));
    update(ch(x,d^1)); update(x);
}

inline void maintain(int x){
    if (t[x].sz==1) return;
    if (t[t[x].l].sz<t[x].sz*alpha) rotate(x,1);
    else if(t[t[x].r].sz<t[x].sz*alpha) rotate(x,0);
}

void Insert(int u,int x){
    if(t[u].sz==1){
        int p=t[u].val,q=x;
        if(p>q) swap(p,q);
        t[u].l=newnode(p),t[u].r=newnode(q);
        update(u);
        return ;
    }
    if(t[t[u].l].val<x) Insert(t[u].r,x);
    else Insert(t[u].l,x);
    update(u); maintain(u);
}
void Delete(int u,int x){
    if(t[t[u].l].val>=x){
        if(t[t[u].l].sz==1) t[u]=t[t[u].r];
        else Delete(t[u].l,x),update(u);
    }
    else{
        if(t[t[u].r].sz==1) t[u]=t[t[u].l];
        else Delete(t[u].r,x),update(u); 
    }
}
int getrnk(int u,int x){
    if(t[u].sz==1) return 1;
    if(t[t[u].l].val<x) return getrnk(t[u].r,x)+t[t[u].l].sz;
    else return getrnk(t[u].l,x);
}
int getkth(int u,int k){
    if(t[u].sz==1) return t[u].val;
    if(t[t[u].l].sz<k) return getkth(t[u].r,k-t[t[u].l].sz);
    else return getkth(t[u].l,k);
}
inline int getlst(int x){
    return getkth(1,getrnk(1,x)-1);
}
inline int getnxt(int x){
    return getkth(1,getrnk(1,x+1));
}

inline int qread(){
    int x=0;char ch;
    while((ch=getchar())&&(ch>'9'||ch<'0')) ;x=(ch^48);
    while((ch=getchar())&&(ch<='9'&&ch>='0')) x=(x<<1)+(x<<3)+(ch^48);
    return x;
}

int main(){
    int n;
    n=qread(),Q=qread();
    newnode(inf);
    for(int i=1;i<=n;i++){
        int x; x=qread();
        Insert(1,x);
    }
    int lst=0;
    int ans=0;
    while(Q--){
        int opt,x;
        opt=qread(),x=qread();x^=lst;
        if(opt==1) Insert(1,x);
        if(opt==2) Delete(1,x);
        if(opt==3) lst=getrnk(1,x),ans^=lst;
        if(opt==4) lst=getkth(1,x),ans^=lst;
        if(opt==5) lst=getlst(x),ans^=lst;
        if(opt==6) lst=getnxt(x),ans^=lst;
    }
    printf("%d",ans);

    return 0;
}