【ybt金牌导航4-3-4】维护集合

维护集合

题目链接：ybt金牌导航4-3-4

题目大意

给你一个集合，初始为空集合。

要你支持一些操作：往集合里放一个数，集合里所有数加或减一个数，求集合里第 k 大的数。

然后还有一个限制条件，如果一个集合里的数小于给定的一个值 Minv，这个数就会被删去。

最后还要输出有多少个数被删去，但往集合里放数时就小于 Minv 而删去的不算入次数中。

思路

看到这种题就容易想到用 Splay 之类的做。

但它要加或减集合里面的数太麻烦，我们考虑把它变成减或加 Minv。

然后你只要把后面读入的数也处理一下，输出的时候处理一下就好了。

剩下的就是平衡树常规操作，直接上 Splay。

代码

#include<cstdio>
#define ll long long

using namespace std;

int ls[300001], rs[300001], fa[300001], size[300001];
ll val[300001];

int n, delete_num, root, tot;
ll Minv, change, x;
char op;

void up(int x) {
	size[x] = size[ls[x]] + size[rs[x]] + 1;
}

bool whs(int x) {
	return x == ls[fa[x]];
}

void Rotate(int x) {
	int y = fa[x];
	int z = fa[y];
	int b = (ls[y] == x) ? rs[x] : ls[x];
	fa[x] = z;
	fa[y] = x;
	if (b) fa[b] = y;
	if (z) ((ls[z] == y) ? ls[z] : rs[z]) = x;
	if (ls[y] == x) ls[y] = b, rs[x] = y;
		else rs[y] = b, ls[x] = y; 
	
	up(y);
	up(x);
}

void Splay(int x, int father) {
	while (fa[x] != father) {
		if (fa[fa[x]] != father) {
			if (whs(x) == whs(fa[x])) Rotate(fa[x]);
				else Rotate(x);
		}
		Rotate(x);
	}
	
	if (!father) root = x;
}

void insert(ll num) {
	int x = root, y = 0, side = 0;
	while (x) {
		y = x;
		size[x]++;
		if (num < val[x]) {
			side = 0;
			x = ls[x];
		}
		else {
			side = 1;
			x = rs[x];
		}
	}
	x = ++tot;
	fa[x] = y;
	val[x] = num;
	size[x] = 1;
	if (y) {
		if (side) rs[y] = x;
			else ls[y] = x;
	}
	
	Splay(x, 0);
}

bool check_pop() {
	int x = root, y = 0;
	while (x) {
		y = x;
		x = ls[x];
	}
	
	Splay(y, 0);
	return val[y] < Minv;
}

int merge(int x, int y) {
	fa[x] = 0;
	fa[y] = 0;
	if (!x) return y;
	if (!y) return x;
	
	int X = x, Y = 0;
	while (X) {
		Y = X;
		X = rs[X];
	}
	Splay(Y, 0);
	rs[Y] = y;
	fa[y] = Y;
	
	return Y;
}

void delete_top() {
	root = merge(ls[root], rs[root]);
}

void delete_minn() {
	int x = root, y = 0;
	while (x) {
		y = x;
		x = ls[x];
	}
	
	Splay(y, 0);
	delete_top(); 
}

int rnk_find_pl(int rnk) {
	rnk = size[root] - rnk + 1;//将求第 k 大转化为求第 n-k+1 小（n 为当前集合点个数）
	int now = root;
	while (now) {
		if (rnk == size[ls[now]] + 1) return now;
		if (rnk < size[ls[now]] + 1) now = ls[now];
			else rnk -= size[ls[now]] + 1, now = rs[now];
	}
}

int main() {
	scanf("%d %lld", &n, &Minv);
	while (n--) {
		op = getchar();
		while (op != 'I' && op != 'A' && op != 'S' && op != 'F') {
			op = getchar();
		}
		
		if (op == 'I') {
			scanf("%lld", &x);
			if (x + change < Minv) continue;
			x += change;//加上这个，防止我们对 Minv 的更改影响了它
			
			insert(x);
		}
		else if (op == 'A') {
			scanf("%lld", &x);
			Minv -= x;//都加一个值 x，相当于 Minx 小了 x
			change -= x;//但后面的数没有加这个值，就相当于后面加的数要减去这个 x
			
			while (root && check_pop()) {
				delete_num++;
				delete_minn();
			}
		}
		else if (op == 'S') {
			scanf("%lld", &x);
			Minv += x;//这个跟加是同理的，只是反过来了而已
			change += x;
			
			while (root && check_pop()) {
				delete_num++;
				delete_minn();
			}
		}
		else {
			scanf("%lld", &x);
			if (size[root] < x) printf("-1\n");
				else printf("%lld\n", val[rnk_find_pl(x)] - change);
				//你输出的时候因为你没有把数加减但其实是它加减，那你还原会真实的就要把之前加或减的退回去
		}
	}
	
	printf("%d", delete_num);
	
	return 0;
}