过了板子题就复制的应该spilt merge kth没问题

t应该也没有开小

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=1000050;
int tot=0;
int root=0;
int n,m;
int x,y,z;

struct Node
{
	int val,rnd;
	int size;
	int ch[2];
}t[N<<1];

void update(int id)
{
	t[id].size=t[t[id].ch[0]].size+t[t[id].ch[1]].size+1;
}

int newNode(int x)
{
	tot++;
	t[tot].size=1;
	t[tot].ch[0]=t[tot].ch[1]=0;
	t[tot].val=x;
	t[tot].rnd=rand();
	return tot;
}

void split(int id,int val,int &x,int &y)
{
	if(!id)
	{
		x=y=0;
		return ;
	}
	if(t[id].val<=val)
	{
		x=id;
		split(t[id].ch[1],val,t[id].ch[1],y);
	}
	else
	{
		y=id;
		split(t[id].ch[0],val,x,t[id].ch[0]);
	}
	update(id);
}

int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(t[x].rnd<t[y].rnd)
	{
		t[x].ch[1]=merge(t[x].ch[1],y);
		update(x);
		return x;
	}
	else
	{
		t[y].ch[0]=merge(x,t[y].ch[0]);
		update(y);
		return y;
	}
}

int kth(int id,int k) 
{
	int ksize=t[t[id].ch[0]].size;
    if(k<=ksize) kth(t[id].ch[0],k);
    else if(k==ksize+1) return t[id].val;
    else kth(t[id].ch[1],k-ksize-1);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int k;
		scanf("%d",&k);
		split(root,k,x,y);
		root=merge(merge(x,newNode(k)),y);
	}	
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		char a[4];
		scanf("%s",a);
		if(a[0]=='a')
		{
			int k;
			scanf("%d",&k);
			split(root,k,x,y);
			root=merge(merge(x,newNode(k)),y);
			n++;
		}
		else
		{	
			int mid;
			mid=(n+1)/2;
			printf("%d\n",kth(root,mid));
		}
	}
	return 0;
}