[NOI 2004] 郁闷的出纳员

题意：维护一个可重集，支持动态插入、查询第k大、给所有数加上或减去一个值，一旦某数小于常数min立即删除，如果插入的数小于min则忽略。最后输出删除的数的个数。 给整棵树打标记即可。原题描述不清，如果插入的数小于min，不纳入最后的统计。

{% raw %}
#include <cstdio>
#include <cstdlib>

const int MAX_N = 1e5 + 1, inf = 1<<30;

struct Node {
	Node* ch[2];
	int v, r, s;
	void up()
	{
		s = ch[0]->s + ch[1]->s + 1;
	}
} nodes[MAX_N], * null = nodes, * root = null;

namespace Treap {
	Node* new_node(int v)
	{
		static Node* cur = nodes+1;
		*cur = (Node){{null, null}, v, rand(), 1};
		return cur++;
	}

	void rotate(Node* &x, int d)
	{
		Node* y = x->ch[d];
		x->ch[d] = y->ch[d^1];
		y->ch[d^1] = x;
		x->up();
		y->up();
		x = y;
	}

	void insert(Node* &x, int v)
	{
		if (x == null)
			x = new_node(v);
		else {
			int d = v > x->v;
			insert(x->ch[d], v);
			if (x->ch[d]->r > x->r)
				rotate(x, d);
			else
				x->up();
		}
	}

	void remove(Node* &x, int v)
	{
		if (x == null)
			return;
		remove(x->ch[0], v);
		if (x->v < v) {
			x = x->ch[1];
			remove(x, v);
		}
		if (x != null)
			x->up();
	}

	int kth(Node* x, int k)
	{
		if (k > x->s)
			return -inf;
		while (x != null) {
			int s = x->ch[1]->s;
			if (s+1 == k)
				return x->v;
			if (k <= s)
				x = x->ch[1];
			else {
				k -= s+1;
				x = x->ch[0];
			}
		}
	}
}

int main()
{
	srand(65535);
	int n, mn, a = 0, cnt = 0;
	scanf("%d %d", &n, &mn);
	while (n--) {
		char c;
		int k, q;
		scanf(" %c %d", &c, &k);
		using namespace Treap;
		switch (c) {
			case 'I':
				if (k >= mn) {
					++cnt;
					insert(root, k-a);
				}
				break;
			case 'A':
				a += k;
				break;
			case 'S':
				a -= k;
				remove(root, mn-a);
				break;
			case 'F':
				q = kth(root, k);
				printf("%d\n", q == -inf ? -1 : q+a);
		}
	}
	printf("%d\n", cnt - root->s);
	return 0;
}
{% endraw %}