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. --- src/main/SetRangeSum.java | 301 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 301 insertions(+) create mode 100644 src/main/SetRangeSum.java (limited to 'src/main') 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