From 50679f7f32fe06e1e1952dc073bcec10d284dec0 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 4 Sep 2019 15:55:37 -0500
Subject: 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.
---
.idea/.gitignore | 3 +
.idea/DataStructureFundamentalJava.iml | 28 +++
.idea/codeStyles/codeStyleConfig.xml | 5 +
.idea/misc.xml | 2 +-
.idea/modules.xml | 8 +
src/main/SetRangeSum.java | 301 +++++++++++++++++++++++++++++++++
6 files changed, 346 insertions(+), 1 deletion(-)
create mode 100644 .idea/.gitignore
create mode 100644 .idea/DataStructureFundamentalJava.iml
create mode 100644 .idea/codeStyles/codeStyleConfig.xml
create mode 100644 .idea/modules.xml
create mode 100644 src/main/SetRangeSum.java
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 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
\ 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 @@
+
+
+
+
+
\ 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 @@
-
+
\ 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 @@
+
+
+
+
+
+
+
+
\ 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);
+ }
+}
+
--
cgit v1.2.3