FHQ 30pts 求调

#include <bits/stdc++.h>
//#define int long long
#define PII pair<int, int>
#define x first
#define y second
#define FH signed

using namespace std;

const int mod1 = 998244353, mod2 = 1e9 + 7, INF = 1e9;
const int N = 1e5 + 10;

int n, m, idx, root;

struct node
{
	int l, r;
	int key;
	short val;
	int size;
} tr[N];

int newnode(int key)
{
	tr[++ idx].l = 0;
	tr[idx].r = 0;
	tr[idx].key = key;
	tr[idx].val = rand();
	tr[idx].size = 1;
	return idx;
}

void updata(int u)
{
	tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}

void split_key(int root, int key, int& x, int& y)
{
	if(root == 0)
	{
		x = y = 0;
		return ;
	}
	if(tr[root].key <= key)
		x = root,
		split_key(tr[root].r, key, tr[root].r, y);
	else
		y = root,
		split_key(tr[root].l, key, x, tr[root].l);
	updata(root);
}

void split_size(int root, int size, int& x, int& y)
{
	if(root == 0)
	{
		x = y = 0;
		return ;
	}
	if(tr[tr[root].l].size + 1 <= size)
		x = root,
		split_size(tr[root].r, size - tr[tr[root].l].size - 1, tr[root].r, y);
	else
		y = root,
		split_size(tr[root].l, size, x, tr[root].l);
	updata(root);
}

int merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(tr[x].val < tr[y].val)
	{
		tr[x].r = merge(tr[x].r, y);
		updata(x);
		return x;
	}
	else
	{
		tr[y].l = merge(x, tr[y].l);
		updata(y);
		return y;
	}
}

void insert(int x)
{
	int t1, t2;
	split_key(root, x, t1, t2);
	root = merge(merge(t1, newnode(x)), t2);
}

int get_key(int x)
{
	int t1, t2, t3;
	split_size(root, x, t1, t2);
	split_size(t1, x - 1, t1, t3);
	int k = tr[t3].key;
	root = merge(merge(t1, t3), t2);
	return k;
}

FH main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	
	cin >> n;
	
	for(int i = 1; i <= n; i ++)
	{
		int a;
		cin >> a;
		insert(a);
	}
	
	cin >> m;
	
	while(m --)
	{
		string s;
		cin >> s;
		if(s == "add")
		{
			int x;
			cin >> x;
			insert(x);
			n ++;
		}
		else
		{
			if(n % 2) cout << get_key((n + 1) / 2) << "\n";
			else cout << min(get_key(n / 2), get_key(n / 2 + 1)) << "\n";
		}
	}
	
	return 0;
}