From d7905f7dec9e306d7d6f907ce35abc40f24af1c5 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 30 Jul 2024 23:58:19 +0200
Subject: more tests

---
 content/datastructures/persistent.cpp      | 8 ++++----
 content/datastructures/persistentArray.cpp | 4 ++--
 2 files changed, 6 insertions(+), 6 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 4093cdc..7d15342 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -4,15 +4,15 @@ struct persistent {
 	vector<pair<int, T>> data;
 
 	persistent(int& time, T value = {}) 
-		: time(time), data(1, {time, value}) {}
+		: time(time), data(1, {2*time, value}) {}
 	
 	T get(int t) {
-		return prev(upper_bound(all(data), pair{t+1, T{}}))->second;
+		return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second;
 	}
 	
 	int set(T value) {
-		time += 2;
-		data.push_back({time, value});
+		time++;
+		data.push_back({2*time, value});
 		return time;
 	}
 };
diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp
index 60d8b17..8326700 100644
--- a/content/datastructures/persistentArray.cpp
+++ b/content/datastructures/persistentArray.cpp
@@ -10,8 +10,8 @@ struct persistentArray {
 	T get(int p, int t) {return data[p].get(t);}
 
 	int set(int p, T value) {
-		mods.push_back({p, time});
-		return data[p].set(value);
+		mods.push_back({p, data[p].set(value)});
+		return mods.back().second;
 	}
 
 	void reset(int t) {
-- 
cgit v1.2.3


From 1ad495344f764e979e93f394f76716cf527c2940 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sun, 4 Aug 2024 15:58:47 +0200
Subject: more tests

---
 content/datastructures/lichao.cpp |   6 ++--
 tcr.pdf                           | Bin 691201 -> 691040 bytes
 test/datastructures/lichao.cpp    |  73 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+), 3 deletions(-)
 create mode 100644 test/datastructures/lichao.cpp

(limited to 'content/datastructures')

diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index f66778e..646ad68 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -11,10 +11,10 @@ struct Lichao {
 	static constexpr Fun id = {0, inf}; // {0, -inf}
 	int n, cap;
 	vector<Fun> seg;
-	Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
+	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
 	
 	void _insert(Fun f, int l, int r, int i) {
-		while (i < 2*cap){
+		while (i < 2 * cap) {
 			int m = (l+r)/2;
 			if (m >= n) {r = m; i = 2*i; continue;}
 			Fun &g = seg[i];
@@ -26,7 +26,7 @@ struct Lichao {
 
 	void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
 		if (l <= a && b <= r) _insert(f, a, b, i);
-		else if (a < r && l < b){
+		else if (a < r && l < b) {
 			int m = (a+b)/2;
 			_segmentInsert(f, l, r, a, m, 2*i);
 			_segmentInsert(f, l, r, m, b, 2*i+1);
diff --git a/tcr.pdf b/tcr.pdf
index 8440c54..1cb888a 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
new file mode 100644
index 0000000..acd048f
--- /dev/null
+++ b/test/datastructures/lichao.cpp
@@ -0,0 +1,73 @@
+#include "../util.h"
+constexpr ll inf = LL::INF;
+#include <datastructures/lichao.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		xs = Random::distinct<ll>(n, -1000, 1000);
+		sort(all(xs));
+
+		vector<ll> naive(n, inf);
+		Lichao tree;
+
+		for (int operations = 0; operations < 1000; operations++) {
+			{
+				ll m = Random::integer<ll>(-100, 100);
+				ll c = Random::integer<ll>(-1000, 1000);
+				ll l = Random::integer<ll>(-1000, 1000);
+				ll r = Random::integer<ll>(-1000, 1000);
+				Fun f{m, c};
+
+				tree.segmentInsert(f, l, r);
+				for (int i = 0; i < n; i++) {
+					if (l <= xs[i] && xs[i] < r) naive[i] = min(naive[i], f(i));
+				}
+			}
+			{
+				queries++;
+				int i = Random::integer<int>(0, n);
+				ll got = tree.query(xs[i]);
+				ll expected = naive[i];
+				if (got != expected) cerr << xs[i] << endl;
+				if (got != expected) cerr << "  got: " << got << ", expected: " << expected << FAIL;
+			}
+		}
+	}
+	cerr << "  tested random queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+
+	t.start();
+	Lichao tree;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+
+		ll m = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll c = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll l = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll r = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = xs[Random::integer<int>(N)];
+		Fun f{m, c};
+
+		t.start();
+		tree.segmentInsert(f, l, r);
+		hash ^= tree.query(x);
+		t.stop();
+	}
+	if (t.time > 1000) cerr << "  too slow: " << t.time << FAIL;
+	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
-- 
cgit v1.2.3


From ff3b67478b1f08b0a2b83565de8a454e23441f3a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 5 Aug 2024 15:41:25 +0200
Subject: more testcases

---
 content/datastructures/monotonicConvexHull.cpp |  18 +++---
 tcr.pdf                                        | Bin 691040 -> 691039 bytes
 test/datastructures/lichao.cpp                 |  22 +++----
 test/datastructures/monotonicConvexHull.cpp    |  79 +++++++++++++++++++++++++
 4 files changed, 100 insertions(+), 19 deletions(-)
 create mode 100644 test/datastructures/monotonicConvexHull.cpp

(limited to 'content/datastructures')

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 44bff83..119015e 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,27 @@
-// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
+// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
 struct Line {
-	ll m, b;
-	ll operator()(ll x) {return m*x+b;}
+	ll m, c;
+	ll operator()(ll x) {return m*x+c;}
 };
 
 vector<Line> ls;
-int ptr = 0;
+ll ptr = 0;
 
 bool bad(Line l1, Line l2, Line l3) {
-	return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
+	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
 }
 
-void add(ll m, ll b) { // Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
+void add(ll m, ll c) { // Laufzeit O(1) amortisiert
+	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
 		ls.pop_back();
 	}
-	ls.push_back({m, b});
+	ls.push_back({m, c});
 	ptr = min(ptr, sz(ls) - 1);
 }
 
 ll query(ll x) { // Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
-	while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
 }
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 1cb888a..48a07d7 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
index acd048f..c8a56a3 100644
--- a/test/datastructures/lichao.cpp
+++ b/test/datastructures/lichao.cpp
@@ -2,11 +2,11 @@
 constexpr ll inf = LL::INF;
 #include <datastructures/lichao.cpp>
 
-void stress_test() {
+void stress_test(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		xs = Random::distinct<ll>(n, -1000, 1000);
+		xs = Random::distinct<ll>(n, -range, range);
 		sort(all(xs));
 
 		vector<ll> naive(n, inf);
@@ -15,9 +15,9 @@ void stress_test() {
 		for (int operations = 0; operations < 1000; operations++) {
 			{
 				ll m = Random::integer<ll>(-100, 100);
-				ll c = Random::integer<ll>(-1000, 1000);
-				ll l = Random::integer<ll>(-1000, 1000);
-				ll r = Random::integer<ll>(-1000, 1000);
+				ll c = Random::integer<ll>(-range, range);
+				ll l = Random::integer<ll>(-range, range);
+				ll r = Random::integer<ll>(-range, range);
 				Fun f{m, c};
 
 				tree.segmentInsert(f, l, r);
@@ -31,11 +31,11 @@ void stress_test() {
 				ll got = tree.query(xs[i]);
 				ll expected = naive[i];
 				if (got != expected) cerr << xs[i] << endl;
-				if (got != expected) cerr << "  got: " << got << ", expected: " << expected << FAIL;
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 			}
 		}
 	}
-	cerr << "  tested random queries: " << queries << endl;
+	cerr << "tested random queries: " << queries << endl;
 }
 
 constexpr int N = 200'000;
@@ -63,11 +63,13 @@ void performance_test() {
 		hash ^= tree.query(x);
 		t.stop();
 	}
-	if (t.time > 1000) cerr << "  too slow: " << t.time << FAIL;
-	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
 int main() {
-	stress_test();
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
 	performance_test();
 }
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
new file mode 100644
index 0000000..0d4e10d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,79 @@
+#include "../util.h"
+struct MCH {
+	#include <datastructures/monotonicConvexHull.cpp>
+};
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		auto ms = Random::distinct<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		sort(all(xs));
+		int i = 0;
+
+		vector<Line> naive;
+
+		MCH mch;
+		for (ll m : ms) {
+			ll c = Random::integer<ll>(-1000, 1000);
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = i + 100; i < j; i++) {
+				ll x = xs[i];
+
+				ll got = mch.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) {
+					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
+					cerr << x << ": " << got << " " << expected << endl;
+				}
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(ms), greater<>{});
+	auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+	MCH mch;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll m = ms[operations];
+		ll x = xs[operations];
+		
+		t.start();
+		mch.add(m, c);
+		hash += mch.query(x);
+		t.stop();
+	}
+	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
-- 
cgit v1.2.3


From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 5 Aug 2024 20:10:57 +0200
Subject: more tests

---
 content/datastructures/dynamicConvexHull.cpp   |   2 +-
 content/datastructures/monotonicConvexHull.cpp |   6 +--
 tcr.pdf                                        | Bin 691039 -> 691129 bytes
 test/datastructures/dynamicConvexHull.cpp      |  72 +++++++++++++++++++++++++
 test/datastructures/monotonicConvexHull.cpp    |   7 +--
 5 files changed, 77 insertions(+), 10 deletions(-)
 create mode 100644 test/datastructures/dynamicConvexHull.cpp

(limited to 'content/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index d669847..dfcfe0b 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -4,7 +4,7 @@ struct Line {
 	bool operator<(ll x) const {return p < x;}
 };
 
-struct HullDynamic : multiset<Line, less<>> {
+struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
 	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
 
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 119015e..e84ad86 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,4 +1,4 @@
-// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue
+// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
 struct Line {
 	ll m, c;
@@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) {
 	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
 }
 
-void add(ll m, ll c) { // Laufzeit O(1) amortisiert
+void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
 	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
 		ls.pop_back();
 	}
@@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 }
 
-ll query(ll x) { // Laufzeit: O(1) amortisiert
+ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
diff --git a/tcr.pdf b/tcr.pdf
index 48a07d7..1b58dc4 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..e0e56ef
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,72 @@
+#include "../util.h"
+namespace dch {
+	constexpr ll INF = LL::INF;
+	#include <datastructures/dynamicConvexHull.cpp>
+}
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+
+		vector<Line> naive;
+
+		dch::HullDynamic hd;
+		for (int i = 0; i < n; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = 0; j < 100; j++) {
+				ll x = Random::integer<ll>(-range, range);
+
+				ll got = hd.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = max(expected, l(x));
+
+				if (got != expected) {
+					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
+					cerr << x << ": " << got << " " << expected << endl;
+				}
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	dch::HullDynamic hd;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		
+		t.start();
+		hd.add(m, c);
+		hash += hd.query(x);
+		t.stop();
+	}
+	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 0d4e10d..4dafbd4 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -23,7 +23,7 @@ void stress_test(ll range) {
 
 		MCH mch;
 		for (ll m : ms) {
-			ll c = Random::integer<ll>(-1000, 1000);
+			ll c = Random::integer<ll>(-range, range);
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
@@ -34,11 +34,6 @@ void stress_test(ll range) {
 				ll expected = naive[0](x);
 				for (auto l : naive) expected = min(expected, l(x));
 
-				if (got != expected) {
-					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
-					cerr << x << ": " << got << " " << expected << endl;
-				}
-
 				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 				queries++;
 			}
-- 
cgit v1.2.3


From 19436370fb48bc0a5e356d1ba713dc39b1a35d3a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 6 Aug 2024 16:54:13 +0200
Subject: upper case INF

---
 content/datastructures/dynamicConvexHull.cpp     |   2 +-
 content/datastructures/lazyPropagation.cpp       |   2 +-
 content/datastructures/lichao.cpp                |   4 ++--
 content/geometry/hpi.cpp                         |   2 +-
 content/other/divideAndConquer.cpp               |   4 ++--
 content/other/knuth.cpp                          |   2 +-
 tcr.pdf                                          | Bin 691129 -> 691160 bytes
 test/datastructures/dynamicConvexHull.lichao.cpp |   1 -
 test/datastructures/lazyPropagation.cpp          |   2 +-
 test/datastructures/lichao.cpp                   |   4 ++--
 test/other/divideAndConquer.cpp                  |   8 ++++----
 test/other/knuth.cpp                             |   8 ++++----
 12 files changed, 19 insertions(+), 20 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index dfcfe0b..27ec898 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -5,7 +5,7 @@ struct Line {
 };
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
-	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
+	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
 	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
 
 	bool isect(iterator x, iterator y) {
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp
index 441590e..ab91364 100644
--- a/content/datastructures/lazyPropagation.cpp
+++ b/content/datastructures/lazyPropagation.cpp
@@ -2,7 +2,7 @@ struct SegTree {
 	using T = ll; using U = ll;
 	int n;
 	static constexpr T E = 0; // Neutral element for combine
-	static constexpr U UF = inf; // Unused value by updates
+	static constexpr U UF = INF; // Unused value by updates
 	vector<T> tree;
 	int h;
 	vector<U> lazy;
diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index 646ad68..1318ca7 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -8,7 +8,7 @@ struct Fun { // Default: Linear function. Change as needed.
 
 // Default: Computes min. Change lines with comment for max.
 struct Lichao {
-	static constexpr Fun id = {0, inf}; // {0, -inf}
+	static constexpr Fun id = {0, INF}; // {0, -INF}
 	int n, cap;
 	vector<Fun> seg;
 	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
@@ -36,7 +36,7 @@ struct Lichao {
 	}
 
 	ll _query(int x) {
-		ll ans = inf; // -inf
+		ll ans = INF; // -INF
 		for (int i = x + cap; i > 0; i /= 2) {
 			ans = min(ans, seg[i](x)); // max
 		}
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index 3509e0e..bd3ab1e 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp
index 830dc7f..9bd5f0c 100644
--- a/content/other/divideAndConquer.cpp
+++ b/content/other/divideAndConquer.cpp
@@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 	if (j1 < j0) return;
 	int jmid = (j0 + j1) / 2;
 
-	dp[i][jmid] = inf;
+	dp[i][jmid] = INF;
 	int bestk = m0;
 	for (int k = m0; k < min(jmid, m1 + 1); ++k) {
 		if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) {
@@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 }
 
 ll calc(int n, int m) {
-	dp = vector<vector<ll>>(m, vector<ll>(n, inf));
+	dp = vector<vector<ll>>(m, vector<ll>(n, INF));
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
 	for (int i = 1; i < m; i++) {
 		rec(i, 0, n - 1, 0, n - 1);
diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp
index 1d513c8..aa54924 100644
--- a/content/other/knuth.cpp
+++ b/content/other/knuth.cpp
@@ -1,5 +1,5 @@
 ll calc(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> dp(m, vector<ll>(n, inf));
+	vector<vector<ll>> dp(m, vector<ll>(n, INF));
 	vector<vector<int>> opt(m, vector<int>(n + 1, n - 1));
 
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
diff --git a/tcr.pdf b/tcr.pdf
index 1b58dc4..649aa24 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
index 6ab55f0..d50ca60 100644
--- a/test/datastructures/dynamicConvexHull.lichao.cpp
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -1,6 +1,5 @@
 #include "../util.h"
 constexpr ll INF = LL::INF;
-constexpr ll inf = LL::INF;
 #include <datastructures/dynamicConvexHull.cpp>
 #include <datastructures/lichao.cpp>
 
diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index 7002061..feb07f0 100644
--- a/test/datastructures/lazyPropagation.cpp
+++ b/test/datastructures/lazyPropagation.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <datastructures/lazyPropagation.cpp>
 
 constexpr int N = 1000'000;
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
index c8a56a3..f4b797b 100644
--- a/test/datastructures/lichao.cpp
+++ b/test/datastructures/lichao.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <datastructures/lichao.cpp>
 
 void stress_test(ll range) {
@@ -9,7 +9,7 @@ void stress_test(ll range) {
 		xs = Random::distinct<ll>(n, -range, range);
 		sort(all(xs));
 
-		vector<ll> naive(n, inf);
+		vector<ll> naive(n, INF);
 		Lichao tree;
 
 		for (int operations = 0; operations < 1000; operations++) {
diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp
index a6fda9d..6d1b444 100644
--- a/test/other/divideAndConquer.cpp
+++ b/test/other/divideAndConquer.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/divideAndConquer.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp
index d469ceb..3462c0a 100644
--- a/test/other/knuth.cpp
+++ b/test/other/knuth.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll iINFnf = LL::INF;
 #include <other/knuth.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
-- 
cgit v1.2.3


From 22536b7fbc050075a1420c0f1a7125b9185c9519 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Mon, 12 Aug 2024 13:22:34 +0200
Subject: add treap test

---
 content/datastructures/datastructures.tex |   2 +-
 content/datastructures/treap.cpp          | 140 +++++++++++++++---------------
 content/datastructures/treap2.cpp         |  79 -----------------
 test/datastructures/treap.cpp             |  85 ++++++++++++++++++
 4 files changed, 156 insertions(+), 150 deletions(-)
 delete mode 100644 content/datastructures/treap2.cpp
 create mode 100644 test/datastructures/treap.cpp

(limited to 'content/datastructures')

diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index 40132a9..c9f3d2a 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -50,7 +50,7 @@
 		\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)}
 		\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
 	\end{methods}
-	\sourcecode{datastructures/treap2.cpp}
+	\sourcecode{datastructures/treap.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Range Minimum Query}
diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c96e36a..c5a60e9 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -1,79 +1,79 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
+mt19937 rng(0xc4bd5dad);
+struct Treap {
+	struct Node {
+		ll val;
+		int prio, size = 1, l = -1, r = -1;
+		Node(ll x) : val(x), prio(rng()) {}
+	};
 
-vector<node> treap;
+	vector<Node> treap;
+	int root = -1;
 
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
+	int getSize(int v) {
+		return v < 0 ? 0 : treap[v].size;
+	}
 
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
+	void upd(int v) {
+		if (v < 0) return;
+		auto& V = treap[v];
+		V.size = 1 + getSize(V.l) + getSize(V.r);
+		// Update Node Code
+	}
 
-pair<int, int> split(int root, int minKeyRight) {
-	if (root < 0) return {-1, -1};
-	if (treap[root].key >= minKeyRight) {
-		auto leftSplit = split(treap[root].left, minKeyRight);
-		treap[root].left = leftSplit.second;
-		update(root);
-		leftSplit.second = root;
-		return leftSplit;
-	} else {
-		auto rightSplit = split(treap[root].right, minKeyRight);
-		treap[root].right = rightSplit.first;
-		update(root);
-		rightSplit.first = root;
-		return rightSplit;
-}}
+	void push(int v) {
+		if (v < 0) return;
+		//auto& V = treap[v];
+		//if (V.lazy) {
+		//	Lazy Propagation Code
+		//	if (V.l >= 0) treap[V.l].lazy = true;
+		//	if (V.r >= 0) treap[V.r].lazy = true;
+		//	V.lazy = false;
+		//}
+	}
 
-int merge (int left, int right) {
-	if (left < 0) return right;
-	if (right < 0) return left;
-	if (treap[left].prio < treap[right].prio) { //min priority heap
-		treap[left].right = merge(treap[left].right, right);
-		update(left);
-		return left;
-	} else {
-		treap[right].left = merge(left, treap[right].left);
-		update(right);
-		return right;
-}}
+	pair<int, int> split(int v, int k) {
+		if (v < 0) return {-1, -1};
+		auto& V = treap[v];
+		push(v);
+		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+			auto [left, right] = split(V.l, k);
+			V.l = right;
+			upd(v);
+			return {left, v};
+		} else {
+			// and only "k"
+			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+			V.r = left;
+			upd(v);
+			return {v, right};
+	}}
 
-//insert values with high priority first
-int insert(int root, int key, int prio) {
-	int next = sz(treap);
-	treap.emplace_back(key, prio);
-	auto t = split(root, key);
-	//returns new root
-	return merge(merge(t.first, next), t.second);
-}
+	int merge(int left, int right) {
+		if (left < 0) return right;
+		if (right < 0) return left;
+		if (treap[left].prio < treap[right].prio) {
+			push(left);
+			treap[left].r = merge(treap[left].r, right);
+			upd(left);
+			return left;
+		} else {
+			push(right);
+			treap[right].l = merge(left, treap[right].l);
+			upd(right);
+			return right;
+	}}
 
-int remove(int root, int key) {
-	if (root < 0) return -1;
-	if (key < treap[root].key) {
-		treap[root].left = remove(treap[root].left, key);
-		update(root);
-		return root;
-	} else if (key > treap[root].key) {
-		treap[root].right = remove(treap[root].right, key);
-		update(root);
-		return root;
-	} else { //check prio?
-		return merge(treap[root].left, treap[root].right);
-}}
+	void insert(int i, ll val) { // and i = val
+		auto [left, right] = split(root, i);
+		treap.emplace_back(val);
+		left = merge(left, sz(treap) - 1);
+		root = merge(left, right);
+	}
 
-int kth(int root, int k) {
-	if (root < 0) return -1;
-	int leftSize = getSize(treap[root].left);
-	if (k < leftSize) return kth(treap[root].left, k);
-	else if (k > leftSize) {
-		return kth(treap[root].right, k - 1 - leftSize);
+	void remove(int i, int count = 1) {
+		auto [left, t_right] = split(root, i);
+		auto [middle, right] = split(t_right, count);
+		root = merge(left, right);
 	}
-	return root;
-}
+	// for query use remove and read middle BEFORE remerging
+};
diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp
deleted file mode 100644
index c5a60e9..0000000
--- a/content/datastructures/treap2.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-mt19937 rng(0xc4bd5dad);
-struct Treap {
-	struct Node {
-		ll val;
-		int prio, size = 1, l = -1, r = -1;
-		Node(ll x) : val(x), prio(rng()) {}
-	};
-
-	vector<Node> treap;
-	int root = -1;
-
-	int getSize(int v) {
-		return v < 0 ? 0 : treap[v].size;
-	}
-
-	void upd(int v) {
-		if (v < 0) return;
-		auto& V = treap[v];
-		V.size = 1 + getSize(V.l) + getSize(V.r);
-		// Update Node Code
-	}
-
-	void push(int v) {
-		if (v < 0) return;
-		//auto& V = treap[v];
-		//if (V.lazy) {
-		//	Lazy Propagation Code
-		//	if (V.l >= 0) treap[V.l].lazy = true;
-		//	if (V.r >= 0) treap[V.r].lazy = true;
-		//	V.lazy = false;
-		//}
-	}
-
-	pair<int, int> split(int v, int k) {
-		if (v < 0) return {-1, -1};
-		auto& V = treap[v];
-		push(v);
-		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
-			auto [left, right] = split(V.l, k);
-			V.l = right;
-			upd(v);
-			return {left, v};
-		} else {
-			// and only "k"
-			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
-			V.r = left;
-			upd(v);
-			return {v, right};
-	}}
-
-	int merge(int left, int right) {
-		if (left < 0) return right;
-		if (right < 0) return left;
-		if (treap[left].prio < treap[right].prio) {
-			push(left);
-			treap[left].r = merge(treap[left].r, right);
-			upd(left);
-			return left;
-		} else {
-			push(right);
-			treap[right].l = merge(left, treap[right].l);
-			upd(right);
-			return right;
-	}}
-
-	void insert(int i, ll val) { // and i = val
-		auto [left, right] = split(root, i);
-		treap.emplace_back(val);
-		left = merge(left, sz(treap) - 1);
-		root = merge(left, right);
-	}
-
-	void remove(int i, int count = 1) {
-		auto [left, t_right] = split(root, i);
-		auto [middle, right] = split(t_right, count);
-		root = merge(left, right);
-	}
-	// for query use remove and read middle BEFORE remerging
-};
diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp
new file mode 100644
index 0000000..ebab34d
--- /dev/null
+++ b/test/datastructures/treap.cpp
@@ -0,0 +1,85 @@
+#include "../util.h"
+#include <datastructures/treap.cpp>
+
+void add(Treap& t, vector<ll>& ans, int v) {
+    if (v < 0) return;
+    add(t, ans, t.treap[v].l);
+    ans.push_back(t.treap[v].val);
+    add(t, ans, t.treap[v].r);
+}
+
+vector<ll> to_vec(Treap& t) {
+    vector<ll> ans;
+    add(t, ans, t.root);
+    return ans;
+}
+
+void stress_test(int T, int n) {
+	for (int tries = 0; tries < T; tries++) {
+		int ins = Random::integer<int>(1, n);
+        int rem = Random::integer<int>(0, ins+1);
+
+        vector<ll> a;
+        Treap t;
+        while (ins + rem > 0) {
+            bool is_ins = Random::integer(0, ins+rem) < ins;
+            if (a.empty()) is_ins = true;
+
+            if (is_ins) {
+                int ind = Random::integer<int>(0, (int)sz(a)+1);
+                ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+                t.insert(ind, val);
+                a.insert(a.begin() + ind, val);
+                ins--;
+            } else {
+                int ind = Random::integer<int>(0, (int)sz(a));
+                int cnt = Random::integer<int>(1, 1 + min<int>({(int)sz(a)-ind, rem, (int)sqrt(n)}));
+                t.remove(ind, cnt);
+                a.erase(a.begin() + ind, a.begin() + ind + cnt);
+                rem -= cnt;
+            }
+        }
+        if (to_vec(t) != a) cerr << "Failed stress test" << endl;
+	}
+	cerr << "Tested " << T << " random tests with n<=" << n << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+
+	t.start();
+	Treap tr;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+        int ind = Random::integer<int>(0, operations+1);
+        ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+
+		t.start();
+        tr.insert(ind, val);
+		hash ^= tr.root;
+		t.stop();
+	}
+    while (tr.root != -1) {
+        t.start();
+        int sz = tr.getSize(tr.root);
+        t.stop();
+
+        int ind = Random::integer<int>(0, sz);
+        int cnt = Random::integer<int>(1, 1 + min<int>(sz-ind, 10));
+        t.start();
+        tr.remove(ind, cnt);
+        t.stop();
+    }
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(10000, 10);
+	stress_test(1000, 100);
+	stress_test(100, 10000);
+	performance_test();
+}
-- 
cgit v1.2.3


From f33aca8fca567c9f318bdd120f20765414ecdf0d Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 01:51:19 +0200
Subject: change style

---
 content/datastructures/persistent.cpp |   2 +-
 content/graph/virtualTree.cpp         |   6 +++---
 tcr.pdf                               | Bin 691136 -> 691284 bytes
 3 files changed, 4 insertions(+), 4 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 7d15342..f26680d 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -7,7 +7,7 @@ struct persistent {
 		: time(time), data(1, {2*time, value}) {}
 	
 	T get(int t) {
-		return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second;
+		return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;
 	}
 	
 	int set(T value) {
diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp
index 27d2d6c..6233b27 100644
--- a/content/graph/virtualTree.cpp
+++ b/content/graph/virtualTree.cpp
@@ -3,13 +3,13 @@ vector<int> in, out;
 
 void virtualTree(vector<int> ind) { // indices of used nodes
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
-	for (int i = 0, n = sz(ind); i < n - 1; i++) {
-		ind.push_back(lca(ind[i], ind[i + 1]));
+	for (int i = 1, n = sz(ind); i < n; i++) {
+		ind.push_back(lca(ind[i - 1], ind[i]));
 	}
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
 	ind.erase(unique(all(ind)), ind.end());
 
-	int n = ind.size();
+	int n = sz(ind);
 	vector<vector<int>> tree(n);
 	vector<int> st = {0};
 	for (int i = 1; i < n; i++) {
diff --git a/tcr.pdf b/tcr.pdf
index 5ebfcb9..b096438 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From f32a00178f0d3b2152a6fc1dc492c987aaede85f Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 17:14:17 +0200
Subject: small improvements

---
 content/datastructures/dynamicConvexHull.cpp |  16 ++++++++--------
 content/datastructures/pbds.cpp              |   4 ++--
 content/geometry/convexHull.cpp              |   4 ++--
 content/geometry/hpi.cpp                     |   2 +-
 content/graph/bitonicTSP.cpp                 |   2 +-
 content/graph/bitonicTSPsimple.cpp           |   2 +-
 content/graph/pushRelabel.cpp                |   2 +-
 tcr.pdf                                      | Bin 691284 -> 691101 bytes
 test/datastructures/fenwickTree2.cpp         |   2 +-
 test/geometry/delaunay.cpp                   |   6 +++---
 test/math/gauss.cpp                          |   2 +-
 test/math/inversionsMerge.cpp                |   2 +-
 12 files changed, 22 insertions(+), 22 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 27ec898..abae1d7 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
 struct Line {
-	mutable ll m, b, p;
+	mutable ll m, c, p;
 	bool operator<(const Line& o) const {return m < o.m;}
 	bool operator<(ll x) const {return p < x;}
 };
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
-	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
-	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
+	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
+	ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
-		else x->p = div(y->b - x->b, x->m - y->m);
+		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
 
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
+	void add(ll m, ll c) {
+		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
 			x--;
@@ -31,6 +31,6 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 
 	ll query(ll x) {
 		auto l = *lower_bound(x);
-		return l.m * x + l.b;
+		return l.m * x + l.c;
 	}
 };
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index f0889a2..de0ace6 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -6,11 +6,11 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 // T.order_of_key(x): number of elements strictly less than x
 // *T.find_by_order(k): k-th element
 
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
 template<typename T>
 struct chash {
-	static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
 	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
+		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
 template<typename K, typename V>
 using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
 			while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index bd3ab1e..c58a6e7 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
 	(lt.back() == 1 ? lt : ut).push_back(0);
 	reverse(all(lt));
 	lt.insert(lt.end(), all(ut));
-	return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
 			rl.push_back(v); p2 = v;
 	}}
 	lr.insert(lr.end(), rl.rbegin(), rl.rend());
-	return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
 	cur.assign(n, 0);
 	H.assign(n, 0);
 	H[s] = n;
-	ec[t] = 1;//never set t to active...
+	ec[t] = 1; //never set t to active...
 	vector<int> co(2*n);
 	co[0] = n - 1;
 	for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/tcr.pdf b/tcr.pdf
index b096438..57691c5 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index aa99576..89d5b0f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -9,7 +9,7 @@ void stress_test() {
 	ll queries = 0;
 	for (int tries = 0; tries < 100; tries++) {
 		int n = Random::integer<int>(10, 100);
-		vector<ll> naive(n);// = Random::integers<ll>(n, -1000, 1000);
+		vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
 		init(naive);
 		for (int operations = 0; operations < 1000; operations++) {
 			{
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 7f8ec30..5740b95 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){
 	vector<pt> h(2 * sz(pts));
 	auto half = [&](auto begin, auto end, int t) {
 		for (auto it = begin; it != end; it++) {
-			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points!
+			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points!
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+	gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
 	vector<vector<double>> res(m);
 	for (int i = 0; i < n; i++) {
 		res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
 	for (ll i = 0; i < 100'000; i++) {
 		int n = Random::integer<int>(1, 100);
 		vector<ll> v(n);
-		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
 		shuffle(all(v), Random::rng);
 		ll expected = naive(v);
 		ll got = mergeSort(v);
-- 
cgit v1.2.3


From 39190436d167414b5853730e91a173fa2affea6a Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 17:15:57 +0200
Subject: small improvements

---
 content/datastructures/dynamicConvexHull.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index abae1d7..63e0e13 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -6,7 +6,7 @@ struct Line {
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
-	ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);}
+	ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-- 
cgit v1.2.3


From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 17 Aug 2024 20:30:08 +0200
Subject: improved monotonic onvex hull

---
 content/datastructures/monotonicConvexHull.cpp |   4 +--
 tcr.pdf                                        | Bin 691092 -> 691111 bytes
 test/datastructures/monotonicConvexHull.cpp    |  41 ++++++++++++++++++++-----
 3 files changed, 35 insertions(+), 10 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index e84ad86..f1721ae 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,5 +1,5 @@
 // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
-// Gerade hat kleinere Steigung als alle vorherigen.
+// Gerade hat kleineres pair(m, c) als alle vorherigen.
 struct Line {
 	ll m, c;
 	ll operator()(ll x) {return m*x+c;}
@@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 }
 
-ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert
+ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
diff --git a/tcr.pdf b/tcr.pdf
index d107dab..199c3de 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 9edfb4b..0415068 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -13,17 +13,30 @@ void stress_test(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		auto ms = Random::distinct<ll>(n, -range, range);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
-		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
+
+		auto xs = Random::integers<ll>(n*100, -range*n, range*n);
 		sort(all(xs));
 		int i = 0;
 
 		vector<Line> naive;
 
 		MCH mch;
-		for (ll m : ms) {
-			ll c = Random::integer<ll>(-range, range);
+		for (int k = 0; k < n; k++) {
+			ll m = ms[k];
+			ll c = cs[k];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
@@ -46,18 +59,30 @@ void stress_test_independent(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		auto ms = Random::distinct<ll>(n, -range, range);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
 
 		vector<Line> naive;
 
 		MCH mch;
-		for (ll m : ms) {
-			ll c = Random::integer<ll>(-range, range);
+		for (int i = 0; i < n; i++) {
+			ll m = ms[i];
+			ll c = cs[i];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
-			auto xs = Random::distinct<ll>(100, -range, range);
+			auto xs = Random::integers<ll>(100, -range, range);
 			sort(all(xs));
 			auto tmp = mch;
 
-- 
cgit v1.2.3