Created
April 4, 2020 08:05
-
-
Save theoremoon/e846138693464ec7310dc507b4a5e9fb to your computer and use it in GitHub Desktop.
This file contains 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; | |
long x, minimum; | |
SplayNode* parent, left, right; | |
void rotate() | |
{ | |
SplayNode* p, pp, 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.relation != 0) | |
{ | |
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 = x; | |
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; | |
} | |
} | |
auto get(SplayNode* root, long i) | |
{ | |
auto now = root; | |
while (true) | |
{ | |
if (i < now.lsize) | |
{ | |
now = now.left; | |
} | |
else if (i == now.lsize) | |
{ | |
now.splay(); | |
return now; | |
} | |
else if (i > now.lsize) | |
{ | |
i = i - now.lsize - 1; | |
now = now.right; | |
} | |
} | |
} | |
auto 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 right = root; | |
auto left = root.left; | |
right.left = null; | |
left.parent = null; | |
right.update(); | |
return tuple(left, right); | |
} | |
auto 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; | |
} | |
auto insert(SplayNode* root, long i, SplayNode* node) | |
{ | |
auto tmp = root.split(i); | |
return merge(merge(tmp[0], node), tmp[1]); | |
} | |
auto 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); | |
} | |
auto shift(SplayNode* root, long l, long r) | |
{ | |
auto tmp = root.remove(r); | |
return tmp[0].insert(l, tmp[1]); | |
} | |
auto getmin(SplayNode* root, long l, long r) | |
{ | |
auto tmp = root.split(r + 1); | |
auto tmp2 = tmp[0].split(l); | |
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", &(nodes[i].x)); | |
nodes[i].update(); | |
} | |
auto root = &nodes[$ - 1]; | |
long x, y, z; | |
foreach (i; 0 .. q) | |
{ | |
readf("%d %d %d\n", &x, &y, &z); | |
if (x == 0) | |
{ | |
// shift | |
root = root.shift(y, z); | |
} | |
else if (x == 1) | |
{ | |
// getmin | |
auto tmp = root.getmin(y, z); | |
root = tmp[0]; | |
writeln(tmp[1]); | |
} | |
else | |
{ | |
// update | |
root = root.get(y); | |
root.x = z; | |
root.update(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment