summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'src/main')
-rw-r--r--src/main/SetRangeSum.java49
1 files changed, 30 insertions, 19 deletions
diff --git a/src/main/SetRangeSum.java b/src/main/SetRangeSum.java
index 8c75189..0d01382 100644
--- a/src/main/SetRangeSum.java
+++ b/src/main/SetRangeSum.java
@@ -8,6 +8,7 @@ public class SetRangeSum {
StringTokenizer st;
boolean eof;
+ // int last_sum_result = 0;
long last_sum_result = 0;
// Splay tree implementation
@@ -190,47 +191,57 @@ public class SetRangeSum {
}
void erase(int x) {
- // Implement erase yourself
+ if (find(x)) {
+ root = merge(root.left, root.right);
+ if (root != null)
+ root.parent = null;
+ return;
+ }
+ }
+
+ boolean find(int x) {
+ if (root != null && root.key == x) return true;
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;
+ if (right == null || right.key != x) {
+ root = merge(left, right);
+ if (right == null)
+ root = splay(left);
+ else
+ root = splay(right);
+ return false;
+ }
+ root = merge(left, right);
+ root = splay(right);
+ return true;
}
long sum(int from, int to) {
+ long ans = 0;
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;
+// ans = ans + left.key;
+// if (middle != null)
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;
+// ans = ans + right.key;
+ root = merge(merge(left, middle), right);
+// last_sum_result = (int) (ans % MODULO);
last_sum_result = ans;
return ans;
+// return last_sum_result;
}
@@ -261,7 +272,7 @@ public class SetRangeSum {
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);
+ last_sum_result = (int) (res % MODULO);
}
}
}