summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.idea/.gitignore3
-rw-r--r--.idea/DataStructureFundamentalJava.iml28
-rw-r--r--.idea/codeStyles/codeStyleConfig.xml5
-rw-r--r--.idea/misc.xml2
-rw-r--r--.idea/modules.xml8
-rw-r--r--src/main/SetRangeSum.java301
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);
+ }
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 13:17:02 +0000