merge mzuenni changes

12 files changed, 712 insertions, 2 deletions

diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp
new file mode 100644
index 0000000..58d76d7
--- /dev/null
+++ b/test/datastructures/LCT.cpp
@@ -0,0 +1,198 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/LCT.cpp>
+
+struct Naive {
+	vector<set<int>> adj;
+	vector<ll> weight;
+	Naive(int n) : adj(n), weight(n, queryDefault) {}
+
+	pair<ll, bool> dfs_path(int from, int to, ll delta = queryDefault, int prev = -1) {
+		if (from == to) {
+			weight[from] += delta;
+			return {weight[from], true};
+		}
+		for (int x : adj[from]) {
+			if (x == prev) continue;
+			auto [res, seen] = dfs_path(x, to, delta, from);
+			if (seen) {
+				weight[from] += delta;
+				return {res + weight[from], true};
+			}
+		}
+		return {queryDefault, false};
+	}
+
+	bool connected(int x, int y) {
+		return dfs_path(x, y).second;
+	}
+
+	void link(int x, int y) {
+		adj[x].insert(y);
+		adj[y].insert(x);
+	}
+
+	void cut(int x, int y) {
+		adj[x].erase(y);
+		adj[y].erase(x);
+	}
+
+	int lca(int root, int a, int b) {
+		int res = -1;
+		auto dfs_lca = [&](auto&& self, int c, int prev = -1) -> pair<bool, bool>{
+			bool seenA = c == a;
+			bool seenB = c == b;
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				auto [tmpA, tmpB] = self(self, x, c);
+				seenA |= tmpA;
+				seenB |= tmpB;
+			}
+			if (seenA && seenB && res < 0) res = c;
+			return {seenA, seenB};
+		};
+		dfs_lca(dfs_lca, root);
+		return res;
+	}
+
+	ll query(int from, int to) {
+		return dfs_path(from, to).first;
+	}
+
+	void modify(int from, int to, ll delta) {
+		dfs_path(from, to, delta);
+	}
+
+	int random(int x) {
+		vector<int> seen;
+		auto dfs_comp = [&](auto&& self, int c, int prev = -1) -> void {
+			seen.push_back(c);
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				self(self, x, c);
+			}
+		};
+		dfs_comp(dfs_comp, x);
+		return seen[Random::integer<int>(sz(seen))];
+	}
+
+	int randomAdj(int x) {
+		if (adj[x].empty()) return -1;
+		vector<int> seen(all(adj[x]));
+		return seen[Random::integer<int>(sz(seen))];
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	ll connected = 0;
+	ll link = 0;
+	ll lca = 0;
+	ll sum = 0;
+	ll modify = 0;
+	ll cut = 0;
+	for (int tries = 0; tries < 500; tries++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(100, 10'000);
+
+		LCT lct(n);
+		Naive naive(n);
+		for (int i = 0; i < m; i++) {
+			bool testConnected = Random::integer<int>(2) == 0;
+			bool testLink = Random::integer<int>(2) == 0;
+			bool testLCA = Random::integer<int>(2) == 0;
+			bool testSum = Random::integer<int>(2) == 0;
+			bool testModify = Random::integer<int>(2) == 0;
+			bool testCut = Random::integer<int>(2) == 0;
+
+			{
+				int a = Random::integer<int>(0, n);
+				int b = Random::integer<int>(0, n);
+
+				auto expected = naive.connected(a, b);
+				if (testConnected) {
+					connected++;
+					auto got = lct.connected(&lct.nodes[a], &lct.nodes[b]);
+					if (got != expected) cerr << "error: 1" << FAIL;
+				}
+
+				if (!expected && testLink) {
+					lct.link(&lct.nodes[a], &lct.nodes[b]);
+					naive.link(a, b);
+					link++;
+					expected = true;
+				}
+
+				if (testLCA && expected) {
+					int c = naive.random(a);
+					lct.makeRoot(&lct.nodes[c]);
+					auto gotLCA = lct.lca(&lct.nodes[a], &lct.nodes[b])->id;
+					auto expectedLCA = naive.lca(c, a, b);
+					if (gotLCA != expectedLCA) cerr << "error: 2" << FAIL;
+					lca++;
+				}
+
+				if (testSum && expected) {
+					auto gotSum = lct.query(&lct.nodes[a], &lct.nodes[b]);
+					auto expectedSum = naive.query(a, b);
+					if (gotSum != expectedSum) cerr << "error: 3" << FAIL;
+					sum++;
+				}
+
+				if (testModify && expected) {
+					ll w = Random::integer<ll>(-1000, 1000);
+					lct.modify(&lct.nodes[a], &lct.nodes[b], w);//must a and b directly connected??
+					naive.modify(a, b, w);
+					modify++;
+				}
+			}
+			{
+				int a = Random::integer<int>(0, n);
+				int b = naive.randomAdj(a);
+				if (b >= 0 && testCut) {
+					lct.cut(&lct.nodes[a], &lct.nodes[b]);
+					naive.cut(a, b);
+					cut++;
+				}
+			}
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	cerr << "  connected: " << connected << endl;
+	cerr << "  link: " << link << endl;
+	cerr << "  lca: " << lca << endl;
+	cerr << "  sum: " << sum << endl;
+	cerr << "  modify: " << modify << endl;
+	cerr << "  cut: " << cut << endl;
+}
+
+constexpr int N = 200'000;
+constexpr int M = 500'000;
+void performance_test() {
+	timer t;
+	t.start();
+	LCT lct(N);
+	t.stop();
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		int a = Random::integer<int>(0, N);
+		int b = Random::integer<int>(0, N);
+		ll w = Random::integer<ll>(-1000, 1000);
+		
+		t.start();
+		if (!lct.connected(&lct.nodes[a], &lct.nodes[b])) {
+			lct.link(&lct.nodes[a], &lct.nodes[b]);
+		}
+		lct.modify(&lct.nodes[a], &lct.nodes[b], w);
+		hash += lct.query(&lct.nodes[a], &lct.nodes[b]);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..e0345af
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,67 @@
+#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) 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 > 200) 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/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
new file mode 100644
index 0000000..d50ca60
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -0,0 +1,37 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <datastructures/dynamicConvexHull.cpp>
+#include <datastructures/lichao.cpp>
+
+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(n, -range, range);
+		sort(all(xs));
+
+		HullDynamic hd;
+		Lichao lichao;
+		for (int i = 0; i < 1000; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			lichao.insert({-m, -c});
+
+			for (ll x : xs) {
+				ll gotA = hd.query(x);
+				ll gotB = -lichao.query(x);
+
+				if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+}
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index d332dc8..bc0753f 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/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index 7b0e448..3030e1c 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
new file mode 100644
index 0000000..f4b797b
--- /dev/null
+++ b/test/datastructures/lichao.cpp
@@ -0,0 +1,75 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <datastructures/lichao.cpp>
+
+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, -range, range);
+		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>(-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);
+				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(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..3ae7c4d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,132 @@
+#include "../util.h"
+#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::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++;
+			}
+		}
+
+		auto xs = Random::integers<ll>(n*100, -range*n, range*n);
+		sort(all(xs));
+		int i = 0;
+
+		vector<Line> naive;
+
+		Envelope mch;
+		for (int k = 0; k < n; k++) {
+			ll m = ms[k];
+			ll c = cs[k];
+
+			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) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+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::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;
+
+		Envelope mch;
+		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::integers<ll>(100, -range, range);
+			sort(all(xs));
+			auto tmp = mch;
+
+			for (auto x : xs) {
+				ll got = tmp.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random independent 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));
+	Envelope 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);
+	stress_test_independent(100);
+	stress_test_independent(1'000);
+	stress_test_independent(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/persistent.cpp b/test/datastructures/persistent.cpp
new file mode 100644
index 0000000..4e304fa
--- /dev/null
+++ b/test/datastructures/persistent.cpp
@@ -0,0 +1,35 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		int timeRef = Random::integer<int>(1, 30);
+		persistent<double> got(timeRef);
+		map<int, double> expected;
+
+		for (int i = 0; i < n; i++) {
+			timeRef += Random::integer<int>(1, 30);
+			double x = Random::real<double>(-1'000, 1'000);
+			auto t = got.set(x);
+
+			if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+			expected[t] = x;
+		}
+
+		double tmp = 0;
+		for (int i = expected.begin()->first; i < expected.rbegin()->first + 10; i++) {
+			if (expected.find(i) != expected.end()) tmp = expected[i];
+			if (got.get(i) != tmp) cerr << "got: " << got.get(i) << ", " << "expected: " << tmp << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp
new file mode 100644
index 0000000..6712089
--- /dev/null
+++ b/test/datastructures/persistentArray.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+#include <datastructures/persistentArray.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 2'000; tries++) {
+		int n = Random::integer<int>(1, 30)*1000;
+		int m = Random::integer<int>(1, 30);
+
+		persistentArray<double> got(m);
+		vector<double> cur(m);
+		vector<pair<int, vector<double>>> expected;
+		for (int i = 0; i < n; i++) {
+			int op = Random::integer<int>(0, 20);
+			if (op <= 10) {
+				int j = Random::integer<int>(0, m);
+				double x = Random::real<double>(-1'000, 1'000);
+
+				auto t = got.set(j, x);
+				if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+
+				cur[j] = x;
+				expected.emplace_back(t, cur);
+			} else if (op <= 16) {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				for (int k = 0; k < m; k++) {
+					if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL;
+				}
+			} else {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				got.reset(expected[j].first);
+				expected.resize(j + 1);
+				cur = expected.back().second;
+			}
+			
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
new file mode 100644
index 0000000..7405e4e
--- /dev/null
+++ b/test/datastructures/stlRope.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlRope.cpp>
+
+int main() {
+	test();
+}
diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk
new file mode 100644
index 0000000..df7c361
--- /dev/null
+++ b/test/datastructures/stlRope.cpp.awk
@@ -0,0 +1,27 @@
+/rope<int> v;/ {
+	print "void test() {"
+	print "ll num = 5;"
+	print "ll start = 2;"
+	print "ll length = 4;"
+	print "ll offset = 3;"
+}
+/v.push_back(num);/ {
+	print "v.push_back(0);"
+	print "v.push_back(1);"
+	print "v.push_back(2);"
+	print "v.push_back(3);"
+	print "v.push_back(4);"
+}
+/rope<int> sub/ {
+	print "v.push_back(6);"
+	print "v.push_back(7);"	
+}
+/for\(auto it/ {
+	print "vector<int> got, expected = {0,1,6,2,3,4,5,7};"
+}
+END {
+	print "	got.push_back(*it);"
+	print "if (got != expected) cerr << \"error\" << endl;"
+	print "}"
+}
+{ print }
diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp
new file mode 100644
index 0000000..2fc9d63
--- /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" << FAIL;
+	}
+	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();
+}