summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
authorHaidong Ji2019-12-01 21:11:57 -0600
committerHaidong Ji2019-12-01 21:11:57 -0600
commita2acdcaa02b85f7733d4b24c75583a502a1a9da4 (patch)
tree3cc25763b34622fdf3588f6117671043776c2fb8 /src/main
parent50679f7f32fe06e1e1952dc073bcec10d284dec0 (diff)
Solved, yay I'm happy. I had to put this aside for a couple of monthsHEADmaster
due to busy work and family life. Yesterday and today I got a little time so I fired up IDEA and started hacking at this again. Lesson learned/reinforced: don't give up, don't dismiss small steps, take those steps like a marathon, and you'll inch closer and finally reach the destination! I found that it helped me that I wrote down those little steps, started them, finished them, and closed them one by one. This gave me momentum to carry it through! Pretty happy about it.
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);
}
}
}