MLE求条

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int n,id,rt;
struct N{
	int ls,rs,v,rd,sz;
}tr[5000010]; 
mt19937 rd(999983);
int nd(int v){
	tr[++id]={0,0,v,rd(),1};
	return id;
}
int pushup(int p){
	tr[p].sz=tr[lc(p)].sz+tr[rc(p)].sz+1;
}
void split(int p,int k,int &x,int &y){
	if(!p){
		x=y=0;
		return ;
	}
	if(tr[lc(p)].sz<k){
		x=p;
		split(rc(p),k-tr[lc(p)].sz-1,rc(p),y);
	}
	else{
		y=p;
		split(lc(p),k,x,lc(p));
	}
	pushup(p);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(tr[x].rd<tr[y].rd){
		rc(x)=merge(rc(x),y);
		pushup(x);
		return x;
	}
	else{
		lc(y)=merge(x,lc(y));
		pushup(y);
		return y;
	}
}
void dfs(int p){
	if(!p)return ;
	dfs(lc(p));
	cout<<tr[p].v<<" ";
	dfs(rc(p));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int v;
		cin>>v;
		int x,y;
		split(rt,v-1,x,y);
		rt=merge(merge(x,nd(i)),y);
	}
	dfs(rt);
	return 0;
}