快读快写

void read(int& x) {
	x = 0;
	int f = 1;

	char ch = getchar();
	while (ch < 48 || ch > 57) {
		if (ch == 45) f = -1;
		ch = getchar();
	}
	while (ch >= 48 && ch <= 57) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}

	x = x * f;
}

void write(int x) {
	if (x < 0) {
		putchar(45);
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}

数组

fact 为实际大小

valid 为有效大小

a 数组用于存中序

int val[100001];
int size_fact[100001];
int size_valid[100001];
int lc[100001];
int rc[100001];
bool exist[100001];
int root;
int num;

double alpha = 0.75;
int a[100001];
int line;

size 更新

inline void update_size(int o)
{
	size_fact[o] = size_fact[lc[o]] + size_fact[rc[o]] + 1;
	size_valid[o] = size_valid[lc[o]] + size_valid[rc[o]] + exist[o];
}

rebuild

void flatten(int o)
{
	if (!o) return;
	flatten(lc[o]);
	if (exist[o]) a[++line] = o;
	flatten(rc[o]);
}

void build(int L, int R, int& o)
{
	int mid = (L + R) >> 1;
	
	o = a[mid];
	lc[o] = rc[o] = 0;
	
	if (L < mid) build(L, mid - 1, lc[o]);
	if (R > mid) build(mid + 1, R, rc[o]);
	update_size(o);
}

void rebuild(int& o)
{
	line = 0;
	flatten(o);
	build(1, line, o);
}

判断是否失衡

inline void judge(int& o)
{
	if (!exist[o]) return;
	if (size_fact[o] * alpha <= (double)max(size_fact[lc[o]], size_fact[rc[o]]) ||
		size_fact[o] * alpha >= (double)size_valid[o])
	rebuild(o);
}

插入和删除

void insert(int& o, int x)
{
	if (!o)
	{
		o = ++num;
		val[o] = x;
		size_fact[o] = size_valid[o] = 1;
		exist[o] = true;
		return;
	}
	
	if (x < val[o])
		insert(lc[o], x);
	else
		insert(rc[o], x);
		
	update_size(o);
	judge(o);
}

void delet(int& o, int x)
{
	if (val[o] == x && exist[o])
	{
		exist[o] = false;
		--size_valid[o];
		--size_fact[o];
		return;
	}
	
	if (x < val[o])
		delet(lc[o], x);
	else
		delet(rc[o], x);
		
	update_size(o);
	judge(o);
}

查询

inline int query_rank(int x)
{
	int o = root;
	int res = 1;
	
	while (o)
	{
		if (x <= val[o]) o = lc[o];
		else
		{
			res += size_valid[lc[o]] + exist[o];
			o = rc[o];
		}
	}
	
	return res;
}

inline int query_num(int k)
{
	int o = root;
	
	while (o)
	{
		if (exist[o] && size_valid[lc[o]] + exist[o] == k) return val[o];
		else if (size_valid[lc[o]] >= k) o = lc[o];
		else
		{
			k -= size_valid[lc[o]] + exist[o];
			o = rc[o];
		}
	}
}

一开始遇到 MLE 是查询的问题，这次不知道是什么，可能也是查询，但是我真的看不出来。

上面的代码中有某些错误使得我 MLE 了 四个点（虽然改了一点之后 MLE 变成了 TLE， 但最初的问题还是 MLE 吧......）

最后，求助于各位大神

sto 神 orz