Luogu P1168 中位数

如何用平衡树水一道绿题 /cy

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int ch[N][2], size[N], val[N], rnd[N], root, tot;
int st[N], top;
int newplace()
{
	if(top)
	{
		return st[top--];
	}
	return ++tot;
}
int newnode(int x)
{
	int ret = newplace();
	ch[ret][0] = ch[ret][1] = 0;
	size[ret] = 1;
	val[ret] = x;
	rnd[ret] = rand();
	return ret;
}
void pushup(int rt)
{
	size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + 1;
	return;
}
int merge(int a, int b)
{
	if(!a || !b)
	{
		return a + b;
	}
	if(rnd[a] < rnd[b])
	{
		ch[a][1] = merge(ch[a][1], b);
		pushup(a);
		return a;
	}
	else
	{
		ch[b][0] = merge(a, ch[b][0]);
		pushup(b);
		return b;
	}
}
void split(int rt, int v, int &x, int &y)
{
	if(!rt)
	{
		x = y = 0;
		return;
	}
	if(val[rt] <= v)
	{
		x = rt;
		split(ch[rt][1], v, ch[rt][1], y);
	}
	else
	{
		y = rt;
		split(ch[rt][0], v, x, ch[rt][0]);
	}
	pushup(rt);
	return;
}
void insert(int &rt, int val)
{
	int x, y;
	split(rt, val, x, y);
	int z = newnode(val);
	rt = merge(merge(x, z), y);
	return;
}
void del(int &rt, int val)
{
	int x, y, z;
	split(rt, val, x, y);
	split(x, val - 1, x, z);
	z = merge(ch[z][0], ch[z][1]);
	rt = merge(merge(x, z), y);
	return;
}
int kth(int rt, int k)
{
	while(rt)
	{
		if(size[ch[rt][0]] + 1 == k)
		{
			return val[rt];
		}
		if(k <= size[ch[rt][0]])
		{
			rt = ch[rt][0];
		}
		else
		{
			k -= size[ch[rt][0]] + 1;
			rt = ch[rt][1];
		}
	}
	return -1;
}
int rank(int &rt, int val)
{
	int x, y;
	split(rt, val - 1, x, y);
	int ret = size[x] + 1;
	rt = merge(x, y);
	return ret;
}
int main()
{
	srand(time(0));
	int n, x;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		insert(root, x);
		if(i & 1)
		{
			printf("%d\n", kth(root, (i + 1) >> 1));
		}
	}
	return 0;
}