BZOJ - 1503 郁闷的出纳员

Posted on | In , ,

思路

A操作由于是对全局节点增加一个值，显然暴力修改不可行，我们考虑使用一个temp保存A和S对数据的加减。由于有一个temp，所以I操作我们需要插入的val改为val-temp。对S，我们插入一个暂时的min-temp，然后删除左子树，然后删除之前插入的那个点。F命令使用FindByRank函数，略微修改下内部参数即可（因为原来是第k多）。本题要注意BZOJ该题使用cin，cout会RE。

Splay

参考了Menci和xehoth的splay模板。吐槽一下这模板怎么删子树是直接改指针的啊？下面的节点直接不回收了。。虽然速度是很快就是了。之前写过一个旋转式的Treap，Splay与它唯一的不同就是Splay操作了，所以这里就记了个内存静态化和Splay操作。

内存静态化

避免了new指针导致空间占用过大的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T, size_t MAXSIZE>
struct MemoryPool {
	T buf[MAXSIZE], *tail, *ext[MAXSIZE];
	int top;
	void init() {
		tail = buf, top = 0;
	}
	T* newnode() {
		return top ? ext[--top] : tail++;
	}
	void retnode(T* rub) {
		ext[top++] = rub;
	}
};

Splay操作

Splay在求前趋，后继，插入，删除的时候都要把修改的节点旋转到根上，使得每个操作的期望复杂度都是log。下面定义目标节点为根（或者是任意你想旋转的节点）的父亲。Splay分三种情况：

  1. 祖父节点为目标节点直接旋转上去
  2. 祖父和父亲的左右儿子关系和父亲与自己左右儿子关系相同，先旋转父亲，再旋转自己
  3. 不然自己做两次旋转

为什么要分2，3的情况？事实上这被称作Splay的双旋，是保证期望时间复杂度为log的重要基础。具体见伸展树splay单旋PK双旋。

参考

Splay 模板 + 详细注释
Splay 学习笔记

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <cstdio>
#include <cstring>
#pragma warning(disable:4996)
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN = 100020;

int n, m;

template<typename T, size_t MAXSIZE>
struct MemoryPool {
	T buf[MAXSIZE], *tail, *ext[MAXSIZE];
	int top;
	void init() {
		tail = buf, top = 0;
	}
	T* newnode() {
		return top ? ext[--top] : tail++;
	}
	void retnode(T* rub) {
		ext[top++] = rub;
	}
};
struct Splay {
	struct node {
		node *child[2], *parent, **root;
		int value, cnt, sizes;
		node() { child[0] = child[1] = NULL; };
		node(node *parent, int value, node **root) :parent(parent), root(root), value(value) {
			child[0] = child[1] = NULL, cnt = sizes = 1;
		}
		int relation() { return parent->child[0] == this ? 0 : 1; }
		void del(MemoryPool<node, MAXN> &pool) {
			if (child[0])pool.retnode(child[0]);
			if (child[1])pool.retnode(child[1]);
		}
		void maintain() {
			sizes = cnt;
			if (child[0])sizes += child[0]->sizes;
			if (child[1])sizes += child[1]->sizes;
		}
		void rotates() {
			int x = relation();
			node *oldParent = parent;
			if (oldParent->parent)oldParent->parent->child[oldParent->relation()] = this;
			parent = oldParent->parent, oldParent->child[x] = child[x ^ 1];
			if (child[x ^ 1])child[x ^ 1]->parent = oldParent;
			child[x ^ 1] = oldParent, oldParent->parent = this, oldParent->maintain(), maintain();
			if (!parent)*root = this;
		}
		void splay(node *targetNode = NULL) {
			while (parent != targetNode) {
				if (parent->parent == targetNode)rotates();
				else if (parent->relation() == relation())parent->rotates(), rotates();
				else rotates(), rotates();
			}
		}
		node* preNode() {
			splay();
			if (!child[0])return NULL;
			else {
				node *v = child[0];
				while (v->child[1])v = v->child[1];
				return v;
			}
		}
		node* nextNode() {
			splay();
			if (!child[1])return NULL;
			else {
				node *v = child[1];
				while (v->child[0])v = v->child[0];
				return v;
			}
		}
		int ranks() {
			return !child[0] ? 0 : child[0]->sizes;
		}
	}*root;
	MemoryPool<node, MAXN> pool;
	void init() {
		root = NULL, pool.init();
	}
	node* findNode(int value) {
		node *v = root;
		while (v&&v->value != value)v = (value<v->value) ? v->child[0] : v->child[1];
		return !v ? NULL : (v->splay(), v);
	}
	node* inserts(int value) {
		node *v = findNode(value);
		if (v) {
			v->cnt++, v->maintain();
			return v;
		}
		node **target = &root, *parent = NULL;
		while (*target)parent = *target, parent->sizes++, target = (value<parent->value) ? &parent->child[0] : &parent->child[1];
		*target = pool.newnode(), (**target) = node(parent, value, &root), (*target)->splay();
		return root;
	}
	void deletes(int value) { deletes(findNode(value)); }
	void deletes(node *v) {
		if (v->cnt != 1) {
			v->splay(), v->cnt--, v->maintain();
			return;
		}
		v->splay();
		if (!v->child[0] && !v->child[1])root = NULL;
		else if (!v->child[0]&&v->child[1])v->child[1]->parent = NULL, root = v->child[1];
		else if (!v->child[1] && v->child[0])v->child[0]->parent = NULL, root = v->child[0];
		else {
			node *pre = v->preNode(), *nexts = v->nextNode();
			pre->splay(), nexts->splay(pre), nexts->child[0]->del(pool);
			pool.retnode(nexts->child[0]), nexts->child[0] = NULL, nexts->maintain(), pre->maintain();
		}
		pool.retnode(v);
	}
	int ranks(int value) {
		node *v = findNode(value);
		if (v)return v->ranks();
		else {
			v = inserts(value);
			int ans = v->ranks();
			deletes(v);
			return ans;
		}
	}
	node* getByRanks(int k) {
		node *v = root;
		while (!(v->ranks() < k && v->ranks() + v->cnt >= k)) v = (k <= v->ranks() ? v->child[0] : (k -= v->ranks() + v->cnt, v->child[1]));
		return v->splay(), v;
	}
	int preNode(int val) {
		node *v = findNode(val);
		if (v)return v->preNode()->value;
		else {
			v = inserts(val);
			int ans = v->preNode()->value;
			deletes(val);
			return ans;
		}
	}
	int nextNode(int val) {
		node *v = findNode(val);
		if (v)return v->nextNode()->value;
		else {
			v = inserts(val);
			int ans = v->nextNode()->value;
			deletes(val);
			return ans;
		}
	}
	void solve() {
		int temp = 0, op, ans = 0;
		char ch;
		for (int i = 0;i<n;i++) {
			scanf(" %c%d", &ch, &op);
			if (ch == 'I') {
				if (op >= m)inserts(op-temp);
			}
			else if (ch == 'A')temp += op;
			else if (ch == 'S') {
				temp -= op;
				node *v = inserts(m - temp);
				v->splay();
				if (v->child[0])ans += v->child[0]->sizes, pool.retnode(v->child[0]);
				v->child[0] = NULL;
				deletes(v);
			}
			else {
				if (!root||op>root->sizes)printf("-1\n");
				else printf("%d\n",getByRanks(root->sizes - op+1)->value + temp);
			}
		}
		printf("%d\n", ans);
	}
}sp;

int main() {
	while (~scanf("%d%d", &n, &m)) {
		sp.init();
		sp.solve();
	}
	return 0;
}