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.

6 files changed, 346 insertions, 1 deletions

diff --git a/.idea/.gitignore b/.idea/.gitignore
new file mode 100644
index 0000000..0e40fe8
--- /dev/null
+++ b/.idea/.gitignore
@@ -0,0 +1,3 @@
+
+# Default ignored files
+/workspace.xml
\ No newline at end of file
diff --git a/.idea/DataStructureFundamentalJava.iml b/.idea/DataStructureFundamentalJava.iml
new file mode 100644
index 0000000..cb888d7
--- /dev/null
+++ b/.idea/DataStructureFundamentalJava.iml
@@ -0,0 +1,28 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module type="JAVA_MODULE" version="4">
+  <component name="NewModuleRootManager" inherit-compiler-output="true">
+    <exclude-output />
+    <content url="file://$MODULE_DIR$">
+      <sourceFolder url="file://$MODULE_DIR$/src/test" isTestSource="true" />
+      <sourceFolder url="file://$MODULE_DIR$/src/main" isTestSource="false" />
+    </content>
+    <orderEntry type="inheritedJdk" />
+    <orderEntry type="sourceFolder" forTests="false" />
+    <orderEntry type="module-library" scope="TEST">
+      <library name="JUnit5.4">
+        <CLASSES>
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter/5.4.2/junit-jupiter-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-api/5.4.2/junit-jupiter-api-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/apiguardian/apiguardian-api/1.0.0/apiguardian-api-1.0.0.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/opentest4j/opentest4j/1.1.1/opentest4j-1.1.1.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/platform/junit-platform-commons/1.4.2/junit-platform-commons-1.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-params/5.4.2/junit-jupiter-params-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-engine/5.4.2/junit-jupiter-engine-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/platform/junit-platform-engine/1.4.2/junit-platform-engine-1.4.2.jar!/" />
+        </CLASSES>
+        <JAVADOC />
+        <SOURCES />
+      </library>
+    </orderEntry>
+  </component>
+</module>
\ No newline at end of file
diff --git a/.idea/codeStyles/codeStyleConfig.xml b/.idea/codeStyles/codeStyleConfig.xml
new file mode 100644
index 0000000..a55e7a1
--- /dev/null
+++ b/.idea/codeStyles/codeStyleConfig.xml
@@ -0,0 +1,5 @@
+<component name="ProjectCodeStyleConfiguration">
+  <state>
+    <option name="PREFERRED_PROJECT_CODE_STYLE" value="Default" />
+  </state>
+</component>
\ No newline at end of file
diff --git a/.idea/misc.xml b/.idea/misc.xml
index 83f45f8..924783f 100644
--- a/.idea/misc.xml
+++ b/.idea/misc.xml
@@ -1,6 +1,6 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <project version="4">
-  <component name="ProjectRootManager" version="2" languageLevel="JDK_1_8" default="false" project-jdk-name="1.8" project-jdk-type="JavaSDK">
+  <component name="ProjectRootManager" version="2" languageLevel="JDK_1_8" default="false" project-jdk-name="1.8.0_222" project-jdk-type="JavaSDK">
     <output url="file://$PROJECT_DIR$/src/out" />
   </component>
 </project>
\ No newline at end of file
diff --git a/.idea/modules.xml b/.idea/modules.xml
new file mode 100644
index 0000000..20ad6c9
--- /dev/null
+++ b/.idea/modules.xml
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="ProjectModuleManager">
+    <modules>
+      <module fileurl="file://$PROJECT_DIR$/.idea/DataStructureFundamentalJava.iml" filepath="$PROJECT_DIR$/.idea/DataStructureFundamentalJava.iml" />
+    </modules>
+  </component>
+</project>
\ No newline at end of file
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);
+    }
+}
+