代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt,t1,t2,t3,rot;

mt19937 rnd(114514);

struct fhq{
	int ls,rs,va,si;
	unsigned pri;
}t[100010];


int ne(int x){
	t[++cnt].va=x;
	t[cnt].pri=rnd();
	t[cnt].si=1;
	return cnt;
}

void pushup(int x){
	t[x].si=t[t[x].ls].si+t[t[x].rs].si+1;
}

void split(int i,int k,int &x,int &y){
	if(!i){ x=y=0; return ;}
	if(k<=t[i].va){
		x=i;
		split(t[i].rs,k,t[i].rs,y);
	}
	else{
		y=i;
		split(t[i].ls,k,x,t[i].ls);
	}
	pushup(i);
}

int merge(int x,int y){
	if(!x || !y ) return x|y;
	if(t[x].pri<t[y].pri){
		t[x].rs=merge(t[x].rs,y);
		pushup(x);
		return x;
	}
	else{
		t[y].ls=merge(x,t[y].ls);
		pushup(y);
		return y;
	}
}

void insert(int x){
	split(rot,x,t1,t2);
	rot=merge(merge(t1,ne(x)),t2);
}

int kth(int i,int k){
	while(1){
		if(t[t[i].ls].si+1==k){
			return t[i].va;
		}
		if(t[t[i].ls].si>=k){
			i=t[i].ls;
		}
		else{
			k-=t[t[i].ls].si+1;
			i=t[i].rs;
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int x,op;
	for(int i=1;i<=n;i++){
		cin>>x;
		insert(x);
	}
	while(m--){
		cin>>op>>x;
		if(op==1){
			cout<<kth(rot,x)<<"\n";
		}
		else{
			insert(x);
		}
	}
}

把t的空间开200005就过了，不知道为什么？有没有大佬讲一下