Salvaged SetRangeSum from the grader and test checkin. The long story

is that I rebuilt the machine from Manjaro to Deepin then back to
Manjaro again. Unfortunately I lost the test file, which I'll recreate.

1 files changed, 301 insertions, 0 deletions

diff --git a/src/main/SetRangeSum.java b/src/main/SetRangeSum.java
new file mode 100644
index 0000000..8c75189
--- /dev/null
+++ b/src/main/SetRangeSum.java
@@ -0,0 +1,301 @@
+import java.io.*;
+import java.util.*;
+
+public class SetRangeSum {
+
+    BufferedReader br;
+    PrintWriter out;
+    StringTokenizer st;
+    boolean eof;
+
+    long last_sum_result = 0;
+    // Splay tree implementation
+
+    // Vertex of a splay tree
+    class Vertex {
+        int key;
+        // Sum of all the keys in the subtree - remember to update
+        // it after each operation that changes the tree.
+        long sum;
+        Vertex left;
+        Vertex right;
+        Vertex parent;
+
+        Vertex(int key, long sum, Vertex left, Vertex right, Vertex parent) {
+            this.key = key;
+            this.sum = sum;
+            this.left = left;
+            this.right = right;
+            this.parent = parent;
+        }
+    }
+
+    void update(Vertex v) {
+        if (v == null) return;
+        v.sum = v.key + (v.left != null ? v.left.sum : 0) + (v.right != null ? v.right.sum : 0);
+        if (v.left != null) {
+            v.left.parent = v;
+        }
+        if (v.right != null) {
+            v.right.parent = v;
+        }
+    }
+
+    void smallRotation(Vertex v) {
+        Vertex parent = v.parent;
+        if (parent == null) {
+            return;
+        }
+        Vertex grandparent = v.parent.parent;
+        if (parent.left == v) {
+            Vertex m = v.right;
+            v.right = parent;
+            parent.left = m;
+        } else {
+            Vertex m = v.left;
+            v.left = parent;
+            parent.right = m;
+        }
+        update(parent);
+        update(v);
+        v.parent = grandparent;
+        if (grandparent != null) {
+            if (grandparent.left == parent) {
+                grandparent.left = v;
+            } else {
+                grandparent.right = v;
+            }
+        }
+    }
+
+    void bigRotation(Vertex v) {
+        if (v.parent.left == v && v.parent.parent.left == v.parent) {
+            // Zig-zig
+            smallRotation(v.parent);
+            smallRotation(v);
+        } else if (v.parent.right == v && v.parent.parent.right == v.parent) {
+            // Zig-zig
+            smallRotation(v.parent);
+            smallRotation(v);
+        } else {
+            // Zig-zag
+            smallRotation(v);
+            smallRotation(v);
+        }
+    }
+
+    // Makes splay of the given vertex and returns the new root.
+    Vertex splay(Vertex v) {
+        if (v == null) return null;
+        while (v.parent != null) {
+            if (v.parent.parent == null) {
+                smallRotation(v);
+                break;
+            }
+            bigRotation(v);
+        }
+        return v;
+    }
+
+    class VertexPair {
+        Vertex left;
+        Vertex right;
+
+        VertexPair() {
+        }
+
+        VertexPair(Vertex left, Vertex right) {
+            this.left = left;
+            this.right = right;
+        }
+    }
+
+    // Searches for the given key in the tree with the given root
+    // and calls splay for the deepest visited node after that.
+    // Returns pair of the result and the new root.
+    // If found, result is a pointer to the node with the given key.
+    // Otherwise, result is a pointer to the node with the smallest
+    // bigger key (next value in the order).
+    // If the key is bigger than all keys in the tree,
+    // then result is null.
+    VertexPair find(Vertex root, int key) {
+        Vertex v = root;
+        Vertex last = root;
+        Vertex next = null;
+        while (v != null) {
+            if (v.key >= key && (next == null || v.key < next.key)) {
+                next = v;
+            }
+            last = v;
+            if (v.key == key) {
+                break;
+            }
+            if (v.key < key) {
+                v = v.right;
+            } else {
+                v = v.left;
+            }
+        }
+        root = splay(last);
+        return new VertexPair(next, root);
+    }
+
+    VertexPair split(Vertex root, int key) {
+        VertexPair result = new VertexPair();
+        VertexPair findAndRoot = find(root, key);
+        root = findAndRoot.right;
+        result.right = findAndRoot.left;
+        if (result.right == null) {
+            result.left = root;
+            return result;
+        }
+        result.right = splay(result.right);
+        result.left = result.right.left;
+        result.right.left = null;
+        if (result.left != null) {
+            result.left.parent = null;
+        }
+        update(result.left);
+        update(result.right);
+        return result;
+    }
+
+    Vertex merge(Vertex left, Vertex right) {
+        if (left == null) return right;
+        if (right == null) return left;
+        while (right.left != null) {
+            right = right.left;
+        }
+        right = splay(right);
+        right.left = left;
+        update(right);
+        return right;
+    }
+
+    // Code that uses splay tree to solve the problem
+
+    Vertex root = null;
+
+    void insert(int x) {
+        Vertex left = null;
+        Vertex right = null;
+        Vertex new_vertex = null;
+        VertexPair leftRight = split(root, x);
+        left = leftRight.left;
+        right = leftRight.right;
+        if (right == null || right.key != x) {
+            new_vertex = new Vertex(x, x, null, null, null);
+        }
+        root = merge(merge(left, new_vertex), right);
+    }
+
+    void erase(int x) {
+        // Implement erase yourself
+        Vertex left = null;
+        Vertex right = null;
+        Vertex new_vertex = null;
+        VertexPair leftRight = split(root, x);
+        left = leftRight.left;
+        right = leftRight.right;
+
+        if (right == null) return;
+
+        new_vertex = right.right;
+        root = merge(left, new_vertex);
+
+    }
+
+    boolean find(int x) {
+        // Implement find yourself
+        VertexPair vertexPair = find(root, x);
+        if (vertexPair.left == null) return false;
+        if (vertexPair.left.key == x)
+            return true;
+        else return false;
+    }
+
+    long sum(int from, int to) {
+        VertexPair leftMiddle = split(root, from);
+        Vertex left = leftMiddle.left;
+        Vertex middle = leftMiddle.right;
+        VertexPair middleRight = split(middle, to + 1);
+        middle = middleRight.left;
+        Vertex right = middleRight.right;
+        long ans = 0;
+        if (left != null && left.key >= from && left.key <= to)
+            ans = ans + left.sum;
+        if (middle != null && middle.key >= from && middle.key <= to)
+            ans = ans + middle.sum;
+        if (right != null && right.key >= from && right.key <= to)
+            ans = ans + right.sum;
+        last_sum_result = ans;
+
+        return ans;
+    }
+
+
+    static final int MODULO = 1000000001;
+
+    void solve() {
+        int n = nextInt();
+        for (int i = 0; i < n; i++) {
+            char type = nextChar();
+            switch (type) {
+                case '+': {
+                    int x = nextInt();
+                    insert((int) ((x + last_sum_result) % MODULO));
+                }
+                break;
+                case '-': {
+                    int x = nextInt();
+                    erase((int) ((x + last_sum_result) % MODULO));
+                }
+                break;
+                case '?': {
+                    int x = nextInt();
+                    out.println(find((int) ((x + last_sum_result) % MODULO)) ? "Found" : "Not found");
+                }
+                break;
+                case 's': {
+                    int l = nextInt();
+                    int r = nextInt();
+                    long res = sum((int) (l + last_sum_result) % MODULO, (int) (r + last_sum_result) % MODULO);
+                    out.println(res);
+                    last_sum_result = (res % MODULO);
+                }
+            }
+        }
+    }
+
+    SetRangeSum() {
+        br = new BufferedReader(new InputStreamReader(System.in));
+        out = new PrintWriter(System.out);
+    }
+
+    public static void main(String[] args) throws IOException {
+        SetRangeSum setRangeSum = new SetRangeSum();
+        setRangeSum.solve();
+        setRangeSum.out.close();
+    }
+
+    String nextToken() {
+        while (st == null || !st.hasMoreTokens()) {
+            try {
+                st = new StringTokenizer(br.readLine());
+            } catch (Exception e) {
+                eof = true;
+                return null;
+            }
+        }
+        return st.nextToken();
+    }
+
+    int nextInt() {
+        return Integer.parseInt(nextToken());
+    }
+
+    char nextChar() {
+        return nextToken().charAt(0);
+    }
+}
+