平衡树模板

lmh_qwq · 2025-09-10 11:11:02 · 个人记录

#include<bits/stdc++.h>
using namespace std;
const int N=100007;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int nV,lson[N],rson[N],sz[N],val[N],rk[N];
int newnode(int v){
    int u=++nV;
    val[u]=v;
    lson[u]=rson[u]=0;
    sz[u]=1;
    rk[u]=rng();
    return u;
}
void pushup(int u){
    sz[u]=sz[lson[u]]+sz[rson[u]]+1;
}
void pushdown(int u){

}
void split(int u,int& x,int& y,int p){
    if (u==0){
        x=y=0;
        return;
    }
    pushdown(u);
    if (sz[lson[u]]+1<=p){
        x=u;
        split(rson[u],rson[x],y,p-sz[lson[u]]-1);
        pushup(x);
    }
    else{
        y=u;
        split(lson[u],x,lson[y],p);
        pushup(y);
    }
}
int merge(int u,int v){
    if (u==0||v==0){
        return u|v;
    }
    if (rk[u]>rk[v]){
        pushdown(u);
        rson[u]=merge(rson[u],v);
        pushup(u);
        return u;
    }
    else{
        pushdown(v);
        lson[v]=merge(u,lson[v]);
        pushup(v);
        return v;
    }
}
int main(){

    return 0;
}