平衡树模板

#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;
}