Frames

Untitled

0
1#include <iostream>
2#include <fstream>
3#include <functional>
4
5std::ostream* debugStream(&std::cout);
6std::ostream& DebugStream()
7{
8 return *debugStream;
9}
10
11bool runPrintTree = true;
12std::ofstream nullStream;
13void BeQuiet()
14{
15 runPrintTree = false;
16 debugStream = &nullStream;
17}
18
19// Splay tree implementation
20
21// Vertex of a splay tree
22struct Vertex {
23 int key;
24 // Sum of all the keys in the subtree - remember to update
25 // it after each operation that changes the tree.
26 long long sum;
27 Vertex* left;
28 Vertex* right;
29 Vertex* parent;
30
31 Vertex(int key, long long sum, Vertex* left, Vertex* right, Vertex* parent)
32 : key(key), sum(sum), left(left), right(right), parent(parent) {}
33};
34
35void printTree(const Vertex * current, int depth = 0)
36{
37 return;
38
39 // if(runPrintTree == false) return;
40 // if(current == nullptr) return;
41
42 // DebugStream() << std::string(depth * 2, ' ') << current->key << ":" << current-> sum;
43
44 // if(current->parent != nullptr) DebugStream() << " (" << current->parent->key << ")";
45 // DebugStream() << std::endl;
46
47 // auto l = current->left;
48 // if(l != nullptr)
49 // {
50 // printTree(l, depth+1);
51 // }
52
53 // auto r = current->right;
54 // if(r != nullptr)
55 // {
56 // printTree(r, depth+1);
57 // }
58}
59
60void update(Vertex* v) {
61 // DebugStream() << " updating ";
62 if (v == NULL) return;
63 // DebugStream() << v->key << std::endl;
64
65 v->sum = v->key + (v->left != NULL ? v->left->sum : 0ll) + (v->right != NULL ? v->right->sum : 0ll);
66 if (v->left != NULL) {
67 v->left->parent = v;
68 }
69 if (v->right != NULL) {
70 v->right->parent = v;
71 }
72}
73
74void small_rotation(Vertex* v) {
75 Vertex* parent = v->parent;
76 if (parent == NULL) {
77 return;
78 }
79 Vertex* grandparent = v->parent->parent;
80 /*
81 p v
82 / \ / \
83 v pr => vl p
84 / \ / \
85vl m m pr
86 */
87 if (parent->left == v) {
88 // DebugStream() << " small rotate right" << std::endl;
89 // DebugStream() << " before----------------------" << std::endl;
90 // printTree(parent, 4);
91
92 Vertex* m = v->right;
93
94 v->parent = parent->parent;
95 v->right = parent;
96 parent->parent = v;
97
98 parent->left = m;
99 if(m != nullptr) m->parent = parent;
100
101 // DebugStream() << " after----------------------" << std::endl;
102 // printTree(v, 4);
103 }
104 /*
105 p v
106 / \ / \
107 pl v => p vr
108 / \ / \
109 m vr pl m
110 */
111 else {
112 // DebugStream() << " small rotate left" << std::endl;
113 Vertex* m = v->left;
114 v->left = parent;
115 parent->right = m;
116 }
117 update(parent);
118 update(v);
119 v->parent = grandparent;
120 if (grandparent != NULL) {
121 if (grandparent->left == parent) {
122 grandparent->left = v;
123 } else {
124 grandparent->right = v;
125 }
126 }
127}
128
129void big_rotation(Vertex* v) {
130 if (v->parent->left == v && v->parent->parent->left == v->parent) {
131 // Zig-zig
132 small_rotation(v->parent);
133 small_rotation(v);
134 } else if (v->parent->right == v && v->parent->parent->right == v->parent) {
135 // Zig-zig
136 small_rotation(v->parent);
137 small_rotation(v);
138 } else {
139 // Zig-zag
140 small_rotation(v);
141 small_rotation(v);
142 }
143}
144
145// Makes splay of the given vertex and makes
146// it the new root.
147void splay(Vertex*& root, Vertex* v) {
148 // DebugStream() << " splaying ";
149 if (v == NULL) return;
150
151 // DebugStream() << v->key << " on top of ";
152 // if(root != nullptr)
153 // {
154 // DebugStream() << root-> key << std::endl;
155 // }
156
157 while (v->parent != NULL) {
158 if (v->parent->parent == NULL) {
159 // DebugStream() << " small_rotation" << std::endl;
160 small_rotation(v);
161 break;
162 }
163 // DebugStream() << " big_rotation" << std::endl;
164 big_rotation(v);
165 }
166
167 // DebugStream() << " changing root" << std::endl;
168 root = v;
169}
170
171// Searches for the given key in the tree with the given root
172// and calls splay for the deepest visited node after that.
173// If found, returns a pointer to the node with the given key.
174// Otherwise, returns a pointer to the node with the smallest
175// bigger key (next value in the order).
176// If the key is bigger than all keys in the tree,
177// returns NULL.
178Vertex* find(Vertex*& root, int key) {
179 // DebugStream() << " finding " << key << std::endl;
180 // DebugStream() << " before----------------------" << std::endl;
181 // printTree(root, 4);
182
183 if( root!= nullptr && root->key == key) return root;
184
185 Vertex* v = root;
186 Vertex* last = root;
187 Vertex* next = NULL;
188 while (v != NULL) {
189 if (v->key >= key && (next == NULL || v->key < next->key)) {
190 next = v;
191 }
192 last = v;
193 if (v->key == key) {
194 break;
195 }
196 if (v->key < key) {
197 v = v->right;
198 } else {
199 v = v->left;
200 }
201 }
202 // if( last != nullptr) DebugStream() << " last is " << last->key <<std::endl;
203 splay(root, last);
204 // DebugStream() << " after----------------------" << std::endl;
205 // printTree(root, 4);
206
207 return next;
208}
209
210void split(Vertex* root, int key, Vertex*& left, Vertex*& right) {
211 // DebugStream() << " splitting " << key << std::endl;
212 right = find(root, key);
213 splay(root, right);
214 if (right == NULL) {
215 // DebugStream() << " right is null " << std::endl;
216 left = root;
217 return;
218 }
219 left = right->left;
220 right->left = NULL;
221 if (left != NULL) {
222 left->parent = NULL;
223 }
224 update(left);
225 update(right);
226}
227
228Vertex* merge(Vertex* left, Vertex* right) {
229 // DebugStream() << " merging" << std::endl;
230 // DebugStream() << " before left----------------------" << std::endl;
231 // printTree(left, 4);
232 // DebugStream() << " before right----------------------" << std::endl;
233 // printTree(right, 4);
234
235 if (left == NULL) return right;
236 if (right == NULL) return left;
237
238 Vertex* min_right = right;
239 while (min_right->left != NULL) {
240 min_right = min_right->left;
241 }
242 splay(right, min_right);
243 right->left = left;
244 update(right);
245
246 // DebugStream() << " after right----------------------" << std::endl;
247 // printTree(right, 4);
248 return right;
249}
250
251// Code that uses splay tree to solve the problem
252
253Vertex* root = NULL;
254
255void insert(int x) {
256 // DebugStream() << "insert " << x << std::endl;
257
258 Vertex* left = NULL;
259 Vertex* right = NULL;
260 Vertex* new_vertex = NULL;
261 split(root, x, left, right);
262 if (right == NULL || right->key != x) {
263 new_vertex = new Vertex(x, x, NULL, NULL, NULL);
264 }
265 root = merge(merge(left, new_vertex), right);
266}
267
268//STDelete(N)
269// Splay(Next(N))
270// Splay(N)
271// Delete(N)
272void erase(int x) {
273 // DebugStream() << "erase " << x;
274 // Implement erase yourself
275
276 if(root == nullptr) return;
277
278 auto node = find(root, x);
279
280 if(node == nullptr)
281 {
282 // DebugStream() << std::endl;
283 return;
284 }
285
286 if(node->key == x)
287 {
288 auto next = node->parent;
289
290 splay(root, next);
291 splay(root, node);
292 root = merge(node->left, node->right);
293
294 if(root != nullptr) root->parent = nullptr;
295 }
296
297 // DebugStream() << " ok" << std::endl;
298}
299
300bool find(int x) {
301 // DebugStream() << "find " << x;
302
303 if(root == nullptr)
304 {
305 // DebugStream() << " not found" << std::endl;
306 return false;
307 }
308
309 auto node = find(root, x);
310
311 if(node == nullptr)
312 {
313 // DebugStream() << " not found" << std::endl;
314 return false;
315 }
316
317 if(node->key == x)
318 {
319 // DebugStream() << " found" << std::endl;
320 return true;
321 }
322 else
323 {
324 // DebugStream() << " not found" << std::endl;
325 return false;
326 }
327}
328
329long long sum(int from, int to) {
330 // DebugStream() << "sum " << from << " " << to << std::endl;;
331
332 Vertex* left = NULL;
333 Vertex* middle = NULL;
334 Vertex* right = NULL;
335 split(root, from, left, middle);
336 split(middle, to + 1, middle, right);
337
338 // DebugStream() << "middle ---------------------" <<std::endl;
339 // printTree(middle);
340 // DebugStream() << "---------------------" <<std::endl;
341
342 long long ans = 0;
343 if(middle != nullptr)
344 {
345 ans = middle->sum;
346 }
347
348 root = merge(merge(left, middle), right);
349 // DebugStream() << " result " << ans << std::endl;
350 return ans;
351}
352
353const int MODULO = 1000000001;
354
355void run(std::istream& in, std::ostream& out)
356{
357 int n;
358 in >> n;
359 // scanf("%d", &n);
360 int last_sum_result = 0;
361 for (int i = 0; i < n; i++) {
362 // DebugStream() << "tree --------------------------------" << std::endl;
363 // printTree(root);
364 // DebugStream() << "--------------------------------" << std::endl;
365 // char buffer[10];
366 // scanf("%s", buffer);
367 std::string buffer;
368 in >> buffer;
369 char type = buffer[0];
370 switch (type) {
371 case '+' : {
372 int x;
373 // scanf("%d", &x);
374 in >> x;
375 insert((x + last_sum_result) % MODULO);
376 } break;
377 case '-' : {
378 int x;
379 // scanf("%d", &x);
380 in >> x;
381 erase((x + last_sum_result) % MODULO);
382 } break;
383 case '?' : {
384 int x;
385 // scanf("%d", &x);
386 in >> x;
387 auto f = find((x + last_sum_result) % MODULO);
388 // printf( ? "Found\n" : "Not found\n");
389 out << (f ? "Found" : "Not found") << std::endl;
390 } break;
391 case 's' : {
392 int l, r;
393 // scanf("%d %d", &l, &r);
394 in >> l >> r;
395 long long res = sum((l + last_sum_result) % MODULO, (r + last_sum_result) % MODULO);
396
397 // printf("%lld\n", res);
398 out << res << std::endl;
399 last_sum_result = int(res % MODULO);
400 }
401 }
402 }
403
404 // DebugStream() << "tree --------------------------------" << std::endl;
405 // printTree(root);
406 // DebugStream() << "--------------------------------" << std::endl;
407}
408
409#ifdef UNITTESTS
410#define CATCH_CONFIG_MAIN
411#include "../../catch.hpp"
412
413//#define BENCHPRESS_CONFIG_MAIN
414//#include "../../../benchpress.hpp"
415
416void test(std::string fileName)
417{
418 BeQuiet();
419
420 root = nullptr;
421 std::ifstream fin{fileName};
422 std::ifstream fexpectedOut{fileName + ".a"};
423 std::stringstream out;
424 run(fin, out);
425 out.seekg(0);
426 std::string actual, expected;
427 while (std::getline(fexpectedOut, expected))
428 {
429 std::getline(out, actual);
430 REQUIRE(expected == actual);
431 }
432}
433
434TEST_CASE("","")
435{
436 //test("./tests/01");
437 // test("./tests/04");
438 // test("./tests/05");
439 // test("./tests/20");
440 // test("./tests/36");
441 test("./tests/83");
442}
443
444// BENCHMARK("file", [&](benchpress::context* ctx) {
445// for (size_t i = 0; i < ctx->num_iterations(); ++i) {
446// root = nullptr;
447// std::string fileName{"./tests/01"};
448// std::ifstream fin{fileName};
449// std::ifstream fexpectedOut{fileName + ".a"};
450// std::stringstream out;
451// run(fin, out);
452// }
453// })
454
455#else
456
457int main(){
458 BeQuiet();
459 run(std::cin, std::cout);
460 return 0;
461}
462
463#endif
464