帮本蒟蒻条： splay，全TLE求助

#include <iostream>
using namespace std;
#define int long long
const int M = 100005;
struct Node
{
	int father;
	int sz;
	int cnt;
	int ch[2];
	int val;
};
Node t[M];
int tot = 0, root = 0;
void push_up(int p)
{
	if (p != 0)
	{
		t[p].sz = t[p].cnt;
		if (t[p].ch[0] != 0)
		{
			t[p].sz += t[p].ch[0];
		}
		if (t[p].ch[1] != 0)
		{
			t[p].sz += t[p].ch[1];
		}
	}
}
bool get(int p)
{
	return (t[t[p].father].ch[1] == p);
}
void turn(int p)
{
	int fa = t[p].father, grand_father = t[fa].father;
	bool flag = get(p);
	t[fa].ch[flag] = t[p].ch[!flag];
	t[t[fa].ch[flag]].father = fa;
	t[p].ch[!flag] = fa;
	t[fa].father = p;
	if (grand_father != 0)
	{
		t[p].father = grand_father;
		if (t[grand_father].ch[0] == fa)
			t[grand_father].ch[0] = p;
		else t[grand_father].ch[1] = p;
	}
	else t[p].father = 0;
	push_up(fa);
	push_up(p);
}
void splay(int p)
{
	while (t[p].father != 0)
	{
		if (t[t[p].father].father != 0)
		{
			if (get(p) == get(t[p].father))
				turn(t[p].father);
			else turn(p);
		}
		turn(p);
	}
	root = p;
}
void insert(int v)
{
	if (root == 0)
	{
		tot++;
		root = tot;
		t[root].father = t[root].ch[0] = t[root].ch[1] = 0;
		t[root].cnt = t[root].sz = 1;
		t[root].val = v;
		return ;
	}
	int tmp = root;
	while (1)
	{
		if (t[tmp].val == v)
		{
			t[tmp].cnt++;
			push_up(tmp);
			push_up(t[tmp].father);
			splay(tmp);
			return ;
		}
		int last = tmp;
		if (v < t[tmp].val)
			tmp = t[tmp].ch[0];
		else tmp = t[tmp].ch[1];
		if (tmp == 0)
		{
			tot++;
			t[tot].ch[0] = t[tot].ch[1] = 0;
			t[tot].father = last;
			t[tot].sz = t[tot].cnt = 1;
			if (v < t[last].val)
				t[last].ch[0] = tot;
			else t[last].ch[1] = tot;
			t[tot].val = v;
			push_up(tot);
			push_up(last);
			splay(tot);
			return ;
		}
	}
}
int kth(int k)
{
	int now = root;
	while (k)
	{
		if (t[now].ch[0] != 0 && k <= t[t[now].ch[0]].sz)
			now = t[now].ch[0];
		else 
		{
			int sum = t[now].cnt;
			if (t[now].ch[0] != 0)
				sum += t[t[now].ch[0]].sz;
			if (k <= sum)
			{
				return t[now].val;
			}
			k -= sum;
			now = t[now].ch[1];
		}
	}
	return 0;
}
signed main()
{
	int m, q;
	cin >> m >> q;
	for (int i=1;i<=m;i++)
	{
		int x;
		cin >> x;
		insert(x);
	}
	for (int i=1;i<=q;i++)
	{
		int c, n;
		cin >> c >> n;
		if (c == 1)
		{
			cout << kth(m-n+1) << '\n';
		}
		else
		{
			insert(n);
			m++;
		}
	}
	return 0;
}

tysm,悬赏关注