Created
March 31, 2020 07:29
-
-
Save theoremoon/06e431cccd1b42906f36f0558618a856 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv, | |
| std.typecons, std.math, std.container, std.format, std.numeric; | |
| struct SplayNode | |
| { | |
| public: | |
| long size; | |
| SplayNode* parent, left, right; | |
| long value, minimum; | |
| void rotate() | |
| { | |
| SplayNode* pp, p, c; | |
| p = this.parent; | |
| pp = p.parent; | |
| if (p.left == &this) | |
| { | |
| c = this.right; | |
| this.right = p; | |
| p.left = c; | |
| } | |
| else | |
| { | |
| c = this.left; | |
| this.left = p; | |
| p.right = c; | |
| } | |
| if (pp && pp.left == p) | |
| { | |
| pp.left = &this; | |
| } | |
| if (pp && pp.right == p) | |
| { | |
| pp.right = &this; | |
| } | |
| this.parent = pp; | |
| p.parent = &this; | |
| if (c) | |
| { | |
| c.parent = p; | |
| } | |
| p.update(); | |
| this.update(); | |
| } | |
| int relation() | |
| { | |
| if (this.parent == null) | |
| { | |
| return 0; | |
| } | |
| if (this.parent.left == &this) | |
| { | |
| return 1; | |
| } | |
| if (this.parent.right == &this) | |
| { | |
| return -1; | |
| } | |
| return 0; | |
| } | |
| void splay() | |
| { | |
| while (this.parent != null) | |
| { | |
| if (this.parent.relation == 0) | |
| { | |
| this.rotate(); | |
| } | |
| else if (this.relation == this.parent.relation) | |
| { | |
| this.parent.rotate(); | |
| this.rotate(); | |
| } | |
| else | |
| { | |
| this.rotate(); | |
| this.rotate(); | |
| } | |
| } | |
| } | |
| void update() | |
| { | |
| this.size = 1 + this.lsize + this.rsize; | |
| this.minimum = this.value; | |
| if (this.left) | |
| { | |
| this.minimum = min(this.minimum, this.left.minimum); | |
| } | |
| if (this.right) | |
| { | |
| this.minimum = min(this.minimum, this.right.minimum); | |
| } | |
| } | |
| long lsize() | |
| { | |
| return (this.left) ? this.left.size : 0; | |
| } | |
| long rsize() | |
| { | |
| return (this.right) ? this.right.size : 0; | |
| } | |
| } | |
| SplayNode* get(SplayNode* root, long i) | |
| { | |
| SplayNode* now = root; | |
| while (true) | |
| { | |
| if (i < now.lsize) | |
| { | |
| now = now.left; | |
| } | |
| if (i == now.lsize) | |
| { | |
| now.splay(); | |
| return now; | |
| } | |
| if (i > now.lsize) | |
| { | |
| i = i - now.lsize - 1; | |
| now = now.right; | |
| } | |
| } | |
| } | |
| Tuple!(SplayNode*, SplayNode*) split(SplayNode* root, long left_cnt) | |
| { | |
| if (left_cnt == 0) | |
| { | |
| return tuple(cast(SplayNode*) null, root); | |
| } | |
| if (left_cnt == root.size) | |
| { | |
| return tuple(root, cast(SplayNode*) null); | |
| } | |
| root = root.get(left_cnt); | |
| auto left = root.left; | |
| auto right = root; | |
| right.left = null; | |
| left.parent = null; | |
| right.update(); | |
| return tuple(left, right); | |
| } | |
| SplayNode* merge(SplayNode* left, SplayNode* right) | |
| { | |
| if (left == null) | |
| { | |
| return right; | |
| } | |
| if (right == null) | |
| { | |
| return left; | |
| } | |
| left = left.get(left.size - 1); | |
| left.right = right; | |
| right.parent = left; | |
| left.update(); | |
| return left; | |
| } | |
| SplayNode* insert(SplayNode* root, long i, SplayNode* node) | |
| { | |
| auto tmp = root.split(i); | |
| return merge(merge(tmp[0], node), tmp[1]); | |
| } | |
| Tuple!(SplayNode*, SplayNode*) remove(SplayNode* root, long i) | |
| { | |
| root = root.get(i); | |
| auto left = root.left; | |
| auto right = root.right; | |
| if (left) | |
| { | |
| left.parent = null; | |
| } | |
| if (right) | |
| { | |
| right.parent = null; | |
| } | |
| root.left = null; | |
| root.right = null; | |
| root.update(); | |
| return tuple(merge(left, right), root); | |
| } | |
| SplayNode* shift(SplayNode* root, long left, long right) | |
| { | |
| auto tmp = root.remove(right); | |
| return tmp[0].insert(left, tmp[1]); | |
| } | |
| Tuple!(SplayNode*, long) query(SplayNode* root, long left, long right) | |
| { | |
| auto tmp = root.split(right + 1); | |
| auto tmp2 = tmp[0].split(left); | |
| auto ans = tmp2[1].minimum; | |
| return tuple(merge(merge(tmp2[0], tmp2[1]), tmp[1]), ans); | |
| } | |
| void main(string[] args) | |
| { | |
| long n, q; | |
| readf("%d %d\n", &n, &q); | |
| auto nodes = new SplayNode[](n); | |
| foreach (i; 0 .. n - 1) | |
| { | |
| nodes[i].parent = &nodes[i + 1]; | |
| nodes[i + 1].left = &nodes[i]; | |
| } | |
| foreach (i; 0 .. n) | |
| { | |
| long a; | |
| readf("%d\n", &a); | |
| nodes[i].value = a; | |
| nodes[i].update(); | |
| } | |
| auto root = &nodes[n - 1]; | |
| foreach (i; 0 .. q) | |
| { | |
| long cmd, l, r; | |
| readf("%d %d %d\n", &cmd, &l, &r); | |
| if (cmd == 0) | |
| { | |
| root = root.shift(l, r); | |
| } | |
| if (cmd == 1) | |
| { | |
| auto tmp = root.query(l, r); | |
| root = tmp[0]; | |
| writeln(tmp[1]); | |
| } | |
| if (cmd == 2) | |
| { | |
| root = root.get(l); | |
| root.value = r; | |
| root.update(); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment