summaryrefslogtreecommitdiff
path: root/src
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
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')
-rw-r--r--src/main/SetRangeSum.java49
-rw-r--r--src/test/SetRangeSumTest.java154
2 files changed, 184 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);
}
}
}
diff --git a/src/test/SetRangeSumTest.java b/src/test/SetRangeSumTest.java
new file mode 100644
index 0000000..60cd5df
--- /dev/null
+++ b/src/test/SetRangeSumTest.java
@@ -0,0 +1,154 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class SetRangeSumTest {
+ @Test
+ void test1() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ assertFalse(setRangeSum.find((int) ((1 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((1 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((1 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((2 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(3, setRangeSum.sum((int) (1 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (2 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((1000000000 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((1000000000 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((1000000000 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((1000000000 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(1, setRangeSum.sum((int) (999999999 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (1000000000 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((2 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((2 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((9 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(10, setRangeSum.sum((int) (0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (9 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ }
+
+ @Test
+ void test2() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ assertFalse(setRangeSum.find((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ }
+
+ @Test
+ void test3() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ setRangeSum.insert((int) ((491572259 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((491572259 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertFalse(setRangeSum.find((int) ((899375874 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(491572259, setRangeSum.sum((int) (310971296 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (877523306 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((352411209 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ }
+
+ @Test
+ void testGraderCase5() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ assertEquals(0, setRangeSum.sum((int) (88127140 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (859949755 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (407584225 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (906606553 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((885530090 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((234423189 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(234423189, setRangeSum.sum((int) (30746291 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (664192454 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((465752492 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(934598870, setRangeSum.sum((int) (848498590 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (481606032 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ }
+
+ @Test
+ void testAchievingBetterUnderstanding() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ setRangeSum.insert((int) ((7 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((7 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((7 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((7 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((3 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((3 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertTrue(setRangeSum.find((int) ((3 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(3, setRangeSum.sum((int) (3 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (3 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ }
+
+ @Test
+ void testGraderCase20() {
+ SetRangeSum setRangeSum = new SetRangeSum();
+
+ assertEquals(0, setRangeSum.sum((int) (40279559 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (89162572 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((774613289 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (869592654 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (915517087 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((165280355 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((776346290 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((221187096 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (421986248 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (742826969 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (83228103 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (852190011 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((640319482 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((528689193 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertFalse(setRangeSum.find((int) ((75245219 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((617070033 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (25751289 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (70170547 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (28248247 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (617849094 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((954357244 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((477444954 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((608389416 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(0, setRangeSum.sum((int) (400483980 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (423330836 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((477444954 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((441393551 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(66257759, setRangeSum.sum((int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((822218158 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((806479414 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(0, setRangeSum.sum((int) (548665149 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (925635534 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((234121006 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((663305907 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(729563666, setRangeSum.sum((int) (314809050 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (685231317 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (487458874 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (602635501 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((918193520 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertFalse(setRangeSum.find((int) ((606474691 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(0, setRangeSum.sum((int) (188185089 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (774086933 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((322445571 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((814123984 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(66257759, setRangeSum.sum((int) (0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (0 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) (689260392 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (827869844 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((204276815 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((66257759 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((488766408 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(0, setRangeSum.sum((int) (412617563 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (631410280 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((463415495 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((601030115 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((776513589 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(601030115, setRangeSum.sum((int) (257003372 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (887483600 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((154047223 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertTrue(setRangeSum.find((int) ((154047223 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertFalse(setRangeSum.find((int) ((219327735 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((978812473 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(1935950040, setRangeSum.sum((int) (978812473 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (154047223 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((718062555 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertFalse(setRangeSum.find((int) ((128066784 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.erase((int) ((15718305 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((754978417 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(1935950040, setRangeSum.sum((int) ((643892549 + setRangeSum.last_sum_result) % SetRangeSum.MODULO), (int) ((819127300 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+// assertEquals(1935950040, setRangeSum.sum((int) (643892549 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (819127300 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((192401474 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertTrue(setRangeSum.find((int) ((643892549 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((638898307 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertFalse(setRangeSum.find((int) ((973173529 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ setRangeSum.insert((int) ((506709268 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((506709268 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((744166533 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.erase((int) ((638898307 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ setRangeSum.insert((int) ((95240753 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ assertEquals(0, setRangeSum.sum((int) ((997348833 + setRangeSum.last_sum_result) % SetRangeSum.MODULO), (int) ((63778002 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertTrue(setRangeSum.find((int) ((31190791 + setRangeSum.last_sum_result) % SetRangeSum.MODULO)));
+ assertEquals(31190791, setRangeSum.sum((int) (21011834 + setRangeSum.last_sum_result) % SetRangeSum.MODULO, (int) (570648768 + setRangeSum.last_sum_result) % SetRangeSum.MODULO));
+ }
+
+}