mzuenni tests

34 files changed, 0 insertions, 1581 deletions

diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp
deleted file mode 100644
index c1dd278..0000000
--- a/datastructures/LCT.cpp
+++ /dev/null
@@ -1,178 +0,0 @@
-constexpr ll queryDefault = 0;
-constexpr ll updateDefault = 0;
-
-ll _modify(ll x, ll y) {
-	return x + y;
-}
-
-ll _query(ll x, ll y) {
-	return x + y;
-}
-
-ll _update(ll delta, int length) {
-	if (delta == updateDefault) return updateDefault;
-	//ll result = delta
-	//for (int i=1; i<length; i++) result = _query(result, delta);
-	return delta * length;
-}
-
-//generic:
-ll joinValueDelta(ll value, ll delta) {
-	if (delta == updateDefault) return value;
-	return _modify(value, delta);
-}
-
-ll joinDeltas(ll delta1, ll delta2) {
-	if (delta1 == updateDefault) return delta2;
-	if (delta2 == updateDefault) return delta1;
-	return _modify(delta1, delta2);
-}
-
-struct LCT {
-	struct Node {
-		ll nodeValue, subTreeValue, delta;
-		bool revert;
-		int id, size;
-		Node *left, *right, *parent;
-
-		Node(int id = 0, int val = queryDefault) :
-			nodeValue(val), subTreeValue(val), delta(updateDefault),
-			revert(false), id(id), size(1),
-			left(nullptr), right(nullptr), parent(nullptr) {}
-
-		bool isRoot() {
-			return !parent || (parent->left != this &&
-			                   parent->right != this);
-		}
-
-		void push() {
-			if (revert) {
-				revert = false;
-				swap(left, right);
-				if (left) left->revert ^= 1;
-				if (right) right->revert ^= 1;
-			}
-			nodeValue = joinValueDelta(nodeValue, delta);
-			subTreeValue = joinValueDelta(subTreeValue,
-			                              _update(delta, size));
-			if (left) left->delta = joinDeltas(left->delta, delta);
-			if (right) right->delta = joinDeltas(right->delta, delta);
-			delta = updateDefault;
-		}
-
-		ll getSubtreeValue() {
-			return joinValueDelta(subTreeValue, _update(delta, size));
-		}
-
-		void update() {
-			subTreeValue = joinValueDelta(nodeValue, delta);
-			size = 1;
-			if (left) {
-				subTreeValue = _query(subTreeValue,
-				                      left->getSubtreeValue());
-				size += left->size;
-			}
-			if (right) {
-				subTreeValue = _query(subTreeValue,
-				                      right->getSubtreeValue());
-				size += right->size;
-		}}
-	};
-
-	vector<Node> nodes;
-
-	LCT(int n) : nodes(n) {
-		for (int i = 0; i < n; i++) nodes[i].id = i;
-	}
-
-	void connect(Node* ch, Node* p, int isLeftChild) {
-		if (ch) ch->parent = p;
-		if (isLeftChild >= 0) {
-			if (isLeftChild) p->left = ch;
-			else p->right = ch;
-	}}
-
-	void rotate(Node* x) {
-		Node* p = x->parent;
-		Node* g = p->parent;
-		bool isRootP = p->isRoot();
-		bool leftChildX = (x == p->left);
-
-		connect(leftChildX ? x->right : x->left, p, leftChildX);
-		connect(p, x, !leftChildX);
-		connect(x, g, isRootP ? -1 : p == g->left);
-		p->update();
-	}
-
-	void splay(Node* x) {
-		while (!x->isRoot()) {
-			Node* p = x->parent;
-			Node* g = p->parent;
-			if (!p->isRoot()) g->push();
-			p->push();
-			x->push();
-			if (!p->isRoot()) rotate((x == p->left) ==
-			                         (p == g->left) ?  p : x);
-			rotate(x);
-		}
-		x->push();
-		x->update();
-	}
-
-	Node* expose(Node* x) {
-		Node* last = nullptr;
-		for (Node* y = x; y; y = y->parent) {
-			splay(y);
-			y->left = last;
-			last = y;
-		}
-		splay(x);
-		return last;
-	}
-
-	void makeRoot(Node* x) {
-		expose(x);
-		x->revert ^= 1;
-	}
-
-	bool connected(Node* x, Node* y) {
-		if (x == y) return true;
-		expose(x);
-		expose(y);
-		return x->parent;
-	}
-
-	void link(Node* x, Node* y) {
-		assert(!connected(x, y)); // not yet connected!
-		makeRoot(x);
-		x->parent = y;
-	}
-
-	void cut(Node* x, Node* y) {
-		makeRoot(x);
-		expose(y);
-		//must be a tree edge!
-		assert(!(y->right != x || x->left != nullptr));
-		y->right->parent = nullptr;
-		y->right = nullptr;
-	}
-
-	Node* lca(Node* x, Node* y) {
-		assert(connected(x, y));
-		expose(x);
-		return expose(y);
-	}
-
-	ll query(Node* from, Node* to) {
-		makeRoot(from);
-		expose(to);
-		if (to) return to->getSubtreeValue();
-		return queryDefault;
-	}
-
-	void modify(Node* from, Node* to, ll delta) {
-		makeRoot(from);
-		expose(to);
-		to->delta = joinDeltas(to->delta, delta);
-	}
-};
diff --git a/datastructures/bitset.cpp b/datastructures/bitset.cpp
deleted file mode 100644
index a89746c..0000000
--- a/datastructures/bitset.cpp
+++ /dev/null
@@ -1,7 +0,0 @@
-bitset<10> bits(0b000010100);
-bits._Find_first(); //2
-bits._Find_next(2); //4
-bits._Find_next(4); //10 bzw. N
-bits[x] = 1;        //not bits.set(x) or bits.reset(x)!
-bits[x].flip();     //not bits.flip(x)!
-bits.count()        //number of set bits
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
deleted file mode 100644
index 43d6dd8..0000000
--- a/datastructures/datastructures.tex
+++ /dev/null
@@ -1,161 +0,0 @@
-\section{Datenstrukturen}
-
-\begin{algorithm}{Segmentbaum}
-	\begin{methods}
-		\method{SegTree}{baut den Baum auf}{n}
-		\method{query}{findet Summe über $[l, r)$}{\log(n)}
-		\method{update}{ändert einen Wert}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/segmentTree.cpp}
-	
-	\subsubsection{Lazy Propagation}
-	Assignment modifications, sum queries \\
-	\method{lower\_bound}{erster Index in $[l, r) \geq x$ (erfordert max-combine)}{\log(n)}
-	\sourcecode{datastructures/lazyPropagation.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Wavelet Tree}
-	\begin{methods}
-		\method{WaveletTree}{baut den Baum auf}{n\*\log(A)}
-		\method{kth}{sort $[l, r)[k]$}{\log(A)}
-		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(A)}
-	\end{methods}
-	$A$ ist die Gr\"o\ss e des Eingabebereichs, d.h.
-	$\mathit{max} - \mathit{min}$.
-	\sourcecode{datastructures/waveletTree.cpp}
-\end{algorithm}
-\columnbreak
-
-\begin{algorithm}{Fenwick Tree}
-	\begin{methods}
-		\method{init}{baut den Baum auf}{n\*\log(n)}
-		\method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
-		\method{update}{addiert ein Delta zu einem Element}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/fenwickTree.cpp}
-	
-	\begin{methods}
-		\method{init}{baut den Baum auf}{n\*\log(n)}
-		\method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
-		\method{update}{addiert ein Delta zu allen Elementen $[l, r)$}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/fenwickTree2.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
-	\sourcecode{datastructures/stlRope.cpp}
-\end{algorithm}
-\columnbreak
-
-\begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
-	\begin{methods}
-		\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}
-\end{algorithm}
-
-\begin{algorithm}{Range Minimum Query}
-	\begin{methods}
-		\method{init}{baut Struktur auf}{n\*\log(n)}
-		\method{queryIdempotent}{Index des Minimums in $[l, r)$}{1}
-	\end{methods}
-	\begin{itemize}
-		\item \code{better}-Funktion muss idempotent sein!
-	\end{itemize}
-	\sourcecode{datastructures/sparseTable.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Range Aggregate Query}
-	\begin{methods}
-		\method{init}{baut Struktur auf}{n\*\log(n)}
-		\method{query}{Aggregat über $[l,r)$}{1}
-	\end{methods}
-	\sourcecode{datastructures/sparseTableDisjoint.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL-Bitset}
-	\sourcecode{datastructures/bitset.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Link-Cut-Tree}
-	\begin{methods}
-		\method{LCT}{baut Wald auf}{n}
-		\method{connected}{prüft ob zwei Knoten im selben Baum liegen}{\log(n)}
-		\method{link}{fügt $\{x,y\}$ Kante ein}{\log(n)}
-		\method{cut}{entfernt $\{x,y\}$ Kante}{\log(n)}
-		\method{lca}{berechnet LCA von $x$ und $y$}{\log(n)}
-		\method{query}{berechnet \code{query} auf den Knoten des $xy$-Pfades}{\log(n)}
-		\method{modify}{erhöht jeden wert auf dem $xy$-Pfad}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/LCT.cpp}
-\end{algorithm}
-\columnbreak
-
-\begin{algorithm}{Policy Based Data Structures}
-	\sourcecode{datastructures/pbds.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Lower Envelope (Convex Hull Optimization)}
-	Um aus einem Lower Envelope einen Upper Envelope zu machen (oder
-	umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
-	\subsubsection{Monotonic}
-	\begin{methods}
-		\method{add}{add line $mx + b$, $m$ is decreasing}{1}
-		\method{query}{minimum value at $x$, $x$ is increasing}{1}
-	\end{methods}
-	\sourcecode{datastructures/monotonicConvexHull.cpp}
-	\subsubsection{Dynamic}
-	\begin{methods}
-		\method{add}{add line $mx + b$}{\log(n)}
-		\method{query}{minimum value at $x$}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/dynamicConvexHull.cpp}
-	\subsubsection{Li Chao Tree}
-	Every pair of functions has at most one intersection.
-
-	\begin{methods}
-		\method{insert}{add function}{\log(|xs|)}
-		\method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)}
-	\end{methods}
-	\sourcecode{datastructures/lichao.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Union-Find}
-	\begin{methods}
-		\method{init}{legt $n$ einzelne Unions an}{n}
-		\method{findSet}{findet den Repräsentanten}{\log(n)}
-		\method{unionSets}{vereint 2 Mengen}{\log(n)}
-		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
-	\end{methods}
-	\sourcecode{datastructures/unionFind.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Union-Find with size}
-	\begin{methods}
-		\method{init}{legt $n$ einzelne Unions an}{n}
-		\method{findSet}{findet den Repräsentanten}{\log(n)}
-		\method{unionSets}{vereint 2 Mengen}{\log(n)}
-		\method{getSize}{zählt Elemente in Menge, die $i$ enthält}{\log(n)}
-		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
-	\end{methods}
-	\sourcecode{datastructures/unionFind2.cpp}
-\end{algorithm}
-\columnbreak
-
-\begin{algorithm}{Persistent}
-	\begin{methods}
-		\method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)}
-		\method{set}{ändert Wert zu Zeitpunkt $t$}{\log(t)}
-		\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
-	\end{methods}
-	\sourcecode{datastructures/persistent.cpp}
-	\sourcecode{datastructures/persistentArray.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
-	\begin{methods}
-		\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/firstUnused.cpp}
-\end{algorithm}
diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
deleted file mode 100644
index 2bd67a6..0000000
--- a/datastructures/dynamicConvexHull.cpp
+++ /dev/null
@@ -1,34 +0,0 @@
-struct Line {
-	mutable ll m, b, p;
-	bool operator<(const Line& o) const {return m < o.m;}
-	bool operator<(ll x) const {return p < x;}
-};
-
-struct HullDynamic : multiset<Line, less<>> {
-	// (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) {
-		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);
-		return x->p >= y->p;
-	}
-
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
-		while (isect(x, next(x))) erase(next(x));
-		if (x != begin()) {
-			--x;
-			while (isect(x, next(x))) erase(next(x));
-		}
-		while (x != begin() && prev(x)->p >= x->p) {
-			--x;
-			isect(x, erase(next(x)));
-	}}
-
-	ll query(ll x) {
-		auto l = *lower_bound(x);
-		return l.m * x + l.b;
-	}
-};
diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp
deleted file mode 100644
index 7013613..0000000
--- a/datastructures/fenwickTree.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-vector<ll> tree;
-
-void update(int i, ll val) {
-	for (i++; i < ssize(tree); i += i & -i) tree[i] += val;
-}
-
-void init(int n) {
-	tree.assign(n + 1, 0);
-}
-
-ll prefix_sum(int i) {
-	ll sum = 0;
-	for (; i > 0; i &= i-1) sum += tree[i];
-	return sum;
-}
diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp
deleted file mode 100644
index 7fcdbb9..0000000
--- a/datastructures/fenwickTree2.cpp
+++ /dev/null
@@ -1,21 +0,0 @@
-vector<ll> add, mul;
-
-void update(int l, int r, ll val) {
-	for (int tl = l + 1; tl < ssize(add); tl += tl & -tl)
-		add[tl] += val, mul[tl] -= val * l;
-	for (int tr = r + 1; tr < ssize(add); tr += tr & -tr)
-		add[tr] -= val, mul[tr] += val * r;
-}
-
-void init(vector<ll> &v) {
-	mul.assign(size(v) + 1, 0);
-	add.assign(size(v) + 1, 0);
-	for(int i = 0; i < ssize(v); i++) update(i, i + 1, v[i]);
-}
-
-ll prefix_sum(int i) {
-	ll res = 0;
-	for (int ti = i; ti > 0; ti &= ti-1)
-		res += add[ti] * i + mul[ti];
-	return res;
-}
diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp
deleted file mode 100644
index 16b0c21..0000000
--- a/datastructures/firstUnused.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-// Erste natürliche Zahl nicht im set used.
-set<int> used;
-int unusedCounter = 1;
-
-int get_first_unused() { // Laufzeit: O(log n) amortisiert.
-	auto it = used.lower_bound(unusedCounter);
-	while (it != used.end() && *it == unusedCounter) {
-		it++;
-		unusedCounter++;
-	}
-	used.insert(unusedCounter);
-	return unusedCounter++;
-}
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp
deleted file mode 100644
index 2202a6f..0000000
--- a/datastructures/lazyPropagation.cpp
+++ /dev/null
@@ -1,84 +0,0 @@
-struct SegTree {
-	using T = ll; using U = ll;
-	static constexpr T E = 0; // Neutral element for combine
-	static constexpr U UF = 0; // Unused value by updates
-	int n;
-	vector<T> tree; vector<U> lazy;
-	int h;
-	vector<ll> k; // size of segments (optional)
-
-	SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n),
-	//SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def),
-			lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) {
-		ranges::copy(a, tree.begin() + n);
-		for (int i = n - 1; i > 0; i--) {
-			k[i] = 2 * k[2 * i];
-			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
-	}}
-
-	T comb(T a, T b) { return a + b; } // Modify this + E
-
-	void apply(int i, U val) { // And this + UF
-		tree[i] = val * k[i];
-		if (i < n) lazy[i] = val; // Don't forget this
-	}
-
-	void push_down(int i) {
-		if (lazy[i] != UF) {
-			apply(2 * i, lazy[i]);
-			apply(2 * i + 1, lazy[i]);
-			lazy[i] = UF;
-	}}
-
-	void push(int i) {
-		for (int s = h; s > 0; s--) push_down(i >> s);
-	}
-
-	void build(int i) {
-		while (i /= 2) {
-			push_down(i);
-			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
-	}}
-
-	void update(int l, int r, U val) {
-		l += n, r += n;
-		int l0 = l, r0 = r;
-		push(l0), push(r0);
-		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) apply(l++, val);
-			if (r&1) apply(--r, val);
-		}
-		build(l0), build(r0);
-	}
-
-	T query(int l, int r) {
-		l += n, r += n;
-		push(l), push(r);
-		T resL = E, resR = E;
-		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) resL = comb(resL, tree[l++]);
-			if (r&1) resR = comb(tree[--r], resR);
-		}
-		return comb(resL, resR);
-	}
-
-	// Optional:
-	ll lower_bound(int l, int r, T x) {
-		l += n, r += n;
-		push(l), push(r - 1);
-		int a[64] = {}, lp = 0, rp = 64;
-		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) a[lp++] = l++;
-			if (r&1) a[--rp] = --r;
-		}
-		for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this
-			while (i < n) {
-				push_down(i);
-				if (tree[2 * i] >= x) i = 2 * i; // And this
-				else i = 2 * i + 1;
-			}
-			return i - n;
-		}
-		return -1;
-	}
-};
diff --git a/datastructures/lichao.cpp b/datastructures/lichao.cpp
deleted file mode 100644
index f66778e..0000000
--- a/datastructures/lichao.cpp
+++ /dev/null
@@ -1,46 +0,0 @@
-vector<ll> xs; // IMPORTANT: Initialize before constructing!
-int findX(int i) {return lower_bound(all(xs), i) - begin(xs);}
-
-struct Fun { // Default: Linear function. Change as needed. 
-	ll m, c;
-	ll operator()(int x) {return m*xs[x] + c;}
-};
-
-// Default: Computes min. Change lines with comment for max.
-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) {}
-	
-	void _insert(Fun f, int l, int r, int i) {
-		while (i < 2*cap){
-			int m = (l+r)/2;
-			if (m >= n) {r = m; i = 2*i; continue;}
-			Fun &g = seg[i];
-			if (f(m) < g(m)) swap(f, g); // >
-			if (f(l) < g(l)) r = m, i = 2*i; // >
-			else l = m, i = 2*i+1;
-	}}
-	void insert(Fun f) {_insert(f, 0, cap, 1);}
-
-	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){
-			int m = (a+b)/2;
-			_segmentInsert(f, l, r, a, m, 2*i);
-			_segmentInsert(f, l, r, m, b, 2*i+1);
-	}}
-	void segmentInsert(Fun f, ll l, ll r) {
-		_segmentInsert(f, findX(l), findX(r), 0, cap, 1);
-	}
-
-	ll _query(int x) {
-		ll ans = inf; // -inf
-		for (int i = x + cap; i > 0; i /= 2) {
-			ans = min(ans, seg[i](x)); // max
-		}
-		return ans;
-	}
-	ll query(ll x) {return _query(findX(x));}
-};
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
deleted file mode 100644
index e7b9b3e..0000000
--- a/datastructures/monotonicConvexHull.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-struct Envelope {
-	struct Line {
-		ll m, b;
-		ll operator()(ll x) { return m*x+b; }
-	};
-
-	vector<Line> ls;
-	int ptr = 0;
-
-	static 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);
-	}
-
-	void add(ll m, ll b) {
-		while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) {
-			ls.pop_back();
-		}
-		ls.push_back({m, b});
-		ptr = min(ptr, sz(ls) - 1);
-	}
-
-	ll query(ll x) {
-		while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
-		return ls[ptr](x);
-	}
-};
diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp
deleted file mode 100644
index a0e5383..0000000
--- a/datastructures/pbds.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#include <ext/pb_ds/priority_queue.hpp>
-template<typename T>
-using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
-auto it = pq.push(5); // O(1)
-pq.modify(it, 6);     // O(log n)
-pq.erase(it);         // O(log n)
-pq.join(pq2);         // O(1)
-pq.swap(pq2);         // O(1)
-
-#include <ext/pb_ds/assoc_container.hpp>
-using namespace __gnu_pbds;
-template<typename T>
-using Tree = tree<T, null_type, less<T>, rb_tree_tag,
-                  tree_order_statistics_node_update>;
-T.order_of_key(x); // number of elements strictly less than x
-auto it = T.find_by_order(k); // k-th element
-
-template<typename T>
-struct chash {
-	const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
-	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
-}};
-template<typename K, typename V>
-using hashMap = gp_hash_table<K, V, chash<K>>;
-template<typename T>
-using hashSet = gp_hash_table<T, null_type, chash<T>>;
diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp
deleted file mode 100644
index 4093cdc..0000000
--- a/datastructures/persistent.cpp
+++ /dev/null
@@ -1,18 +0,0 @@
-template<typename T>

-struct persistent {

-	int& time;

-	vector<pair<int, T>> data;

-

-	persistent(int& time, T value = {}) 

-		: time(time), data(1, {time, value}) {}

-	

-	T get(int t) {

-		return prev(upper_bound(all(data), pair{t+1, T{}}))->second;

-	}

-	

-	int set(T value) {

-		time += 2;

-		data.push_back({time, value});

-		return time;

-	}

-};

diff --git a/datastructures/persistentArray.cpp b/datastructures/persistentArray.cpp
deleted file mode 100644
index 60d8b17..0000000
--- a/datastructures/persistentArray.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-template<typename T>

-struct persistentArray {

-	int time;

-	vector<persistent<T>> data;

-	vector<pair<int, int>> mods;

-

-	persistentArray(int n, T value = {}) 

-		: time(0), data(n, {time, value}) {}

-

-	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);

-	}

-

-	void reset(int t) {

-		while (!mods.empty() && mods.back().second > t) {

-			data[mods.back().first].data.pop_back();

-			mods.pop_back();

-		}

-		time = t;

-	}

-};

diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp
deleted file mode 100644
index 1fbf886..0000000
--- a/datastructures/segmentTree.cpp
+++ /dev/null
@@ -1,43 +0,0 @@
-struct SegTree {
-	using T = ll;
-	int n;
-	vector<T> tree;
-	static constexpr T E = 0; // Neutral element for combine
-
-	SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) {
-		ranges::copy(a, tree.begin() + n);
-	//SegTree(int size, T val = E) : n(size), tree(2 * n, E) {
-	//	fill(tree.begin() + n, tree.end(), val);
-		for (int i = n - 1; i > 0; i--) { // remove for range update
-			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
-	}}
-
-	T comb(T a, T b) { return a + b; } // modify this + neutral
-
-	void update(int i, T val) {
-		tree[i += n] = val; // apply update code
-		while (i /= 2) tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
-	}
-
-	T query(int l, int r) {
-		T resL = E, resR = E;
-		for (l += n, r += n; l < r; l /= 2, r /= 2) {
-			if (l&1) resL = comb(resL, tree[l++]);
-			if (r&1) resR = comb(tree[--r], resR);
-		}
-		return comb(resL, resR);
-	}
-
-	// OR: range update + point query, needs commutative comb
-	void modify(int l, int r, T val) {
-		for (l += n, r += n; l < r; l /= 2, r /= 2) {
-			if (l&1) tree[l] = comb(tree[l], val), l++;
-			if (r&1) --r, tree[r] = comb(tree[r], val);
-	}}
-
-	T query(int i) {
-		T res = E;
-		for (i += n; i > 0; i /= 2) res = comb(res, tree[i]);
-		return res;
-	}
-};
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
deleted file mode 100644
index 64a892a..0000000
--- a/datastructures/sparseTable.cpp
+++ /dev/null
@@ -1,23 +0,0 @@
-struct SparseTable {
-	vector<vector<int>> st;
-	ll *a;
-
-	int better(int lidx, int ridx) {
-		return a[lidx] <= a[ridx] ? lidx : ridx;
-	}
-
-	void init(vector<ll> &vec) {
-		int n = sz(vec);
-		a = vec.data();
-		st.assign(__lg(n) + 1, vector<int>(n));
-		iota(all(st[0]), 0);
-		for (int j = 0; (2 << j) <= n; j++) {
-			for (int i = 0; i + (2 << j) <= n; i++) {
-				st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]);
-	}}}
-
-	int queryIdempotent(int l, int r) {
-		int j = __lg(r - l); //31 - builtin_clz(r - l);
-		return better(st[j][l] , st[j][r - (1 << j)]);
-	}
-};
diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp
deleted file mode 100644
index dc5297a..0000000
--- a/datastructures/sparseTableDisjoint.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-struct DisjointST {
-	static constexpr ll neutral = 0;
-	vector<vector<ll>> dst;
-	ll* a;
-
-	ll combine(const ll& x, const ll& y) {
-		return x + y;
-	}
-
-	void init(vector<ll> &vec) {
-		int n = sz(vec);
-		a = vec.data();
-		dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral));
-		for (int h = 0, l = 1; l <= n; h++, l *= 2) {
-			for (int c = l; c < n + l; c += 2 * l) {
-				for (int i = c; i < min(n, c + l); i++)
-					dst[h][i + 1] = combine(dst[h][i], vec[i]);
-				for (int i = min(n, c); i > c - l; i--)
-					dst[h][i - 1] = combine(vec[i - 1], dst[h][i]);
-	}}}
-
-	ll query(int l, int r) {
-		int h = __lg(l ^ r);
-		return combine(dst[h][l], dst[h][r]);
-	}
-};
diff --git a/datastructures/stlRope.cpp b/datastructures/stlRope.cpp
deleted file mode 100644
index 804cd67..0000000
--- a/datastructures/stlRope.cpp
+++ /dev/null
@@ -1,8 +0,0 @@
-#include <ext/rope>
-using namespace __gnu_cxx;
-rope<int> v; // Wie normaler Container.
-v.push_back(num); // O(log(n))
-rope<int> sub = v.substr(start, length); // O(log(n))
-v.erase(start, length); // O(log(n))
-v.insert(v.mutable_begin() + offset, sub); // O(log(n))
-for(auto it = v.mutable_begin(); it != v.mutable_end(); it++)
diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
deleted file mode 100644
index f9dd619..0000000
--- a/datastructures/test/fenwickTree.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#include "../fenwickTree.cpp"
-
-void test(int n) {
-	vector<ll> naive(n);
-	init(n);
-
-	for (int i = 0; i < 1000; i++) {
-		int p = util::randint(n);
-		ll delta = util::randint();
-		update(p, delta);
-		naive[p] += delta;
-
-		int r = util::randint(n+1);
-
-		ll naive_result = 0;
-		for (int i = 0; i < r; i++) naive_result += naive[i];
-		ll fenwick_result = prefix_sum(r);
-		assert(naive_result == fenwick_result);
-	}
-}
-
-int main() {
-	test(1);
-	test(100);
-	test(1000);
-}
diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp
deleted file mode 100644
index 18ebcb7..0000000
--- a/datastructures/test/fenwickTree2.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include "../fenwickTree2.cpp"
-
-void test(int n) {
-	vector<ll> naive(n);
-	for (int i = 0; i < n; i++) naive[i] = util::randint();
-	init(naive);
-
-	for (int i = 0; i < 1000; i++) {
-		int l = util::randint(n), r = util::randint(n);
-		if (l > r) swap(l, r);
-		ll delta = util::randint();
-		update(l, r, delta);
-		for (int i = l; i < r; i++) naive[i] += delta;
-
-		r = util::randint(n+1);
-
-		ll naive_result = 0;
-		for (int i = 0; i < r; i++) naive_result += naive[i];
-		ll fenwick_result = prefix_sum(r);
-		assert(naive_result == fenwick_result);
-	}
-}
-
-int main() {
-	test(1);
-	test(100);
-	test(1000);
-}
diff --git a/datastructures/test/lazyPropagation.awk b/datastructures/test/lazyPropagation.awk
deleted file mode 100644
index fc39305..0000000
--- a/datastructures/test/lazyPropagation.awk
+++ /dev/null
@@ -1,86 +0,0 @@
-
-/Neutral element for combine/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print "# ifndef SEGTREE_MAX"
-	print
-	print "# else"
-	tmp = $0
-	sub(/0/, "numeric_limits<T>::min()", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/0/, "numeric_limits<T>::max()")
-	print
-	print "#endif"
-	next
-}
-
-/Modify this \+ E/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print "# ifndef SEGTREE_MAX"
-	print
-	print "# else"
-	tmp = $0
-	sub(/a \+ b/, "max(a, b)", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/a \+ b/, "a < 0 ? a : min(a, b)")
-	print
-	print "#endif"
-	next
-}
-
-/Unused value by updates/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print
-	print "#else"
-	sub(/0/, /numeric_limits<U>::max()/)
-	print
-	print "#endif"
-	next
-}
-
-/And this \+ UF/ {
-	print
-	getline set_tree
-	getline set_lazy
-	print "#ifndef SEGTREE_MAX"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print set_tree
-	print "# else"
-	tmp = set_tree
-	sub(/val \* k\[i\]/, "val", tmp)
-	print tmp
-	print "# endif"
-	print set_lazy
-	print "#else"
-	sub(/= val \* k\[i\]/, "+= val", set_tree)
-	sub(/= val/, "+= val", set_lazy)
-	print set_tree
-	print set_lazy
-	print "#endif"
-	next
-}
-
-/Optional/ { print "#ifdef SEGTREE_MAX" }
-/^\};$/ { print "#endif" }
-
-/SegTree\(const vector<T>& a\)/ {
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	print
-	print "#else"
-	getline
-	sub(/\/\//, "")
-	print
-	print "#endif"
-	getline
-	print
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	getline
-	print
-	print "#endif"
-	next
-}
-
-{ print }
diff --git a/datastructures/test/lazyPropagation.cpp b/datastructures/test/lazyPropagation.cpp
deleted file mode 100644
index df97b14..0000000
--- a/datastructures/test/lazyPropagation.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
-#include "lazyPropagation.tmp.cpp"
-
-void test(int n) {
-#ifndef SEGTREE_INIT_DEFAULT
-	vector<ll> a(n);
-	for (ll &x: a) x = util::randint();
-	SegTree seg(a);
-#else
-	ll init = util::randint();
-# ifdef SEGTREE_FIRST_NEG
-	init = abs(init);
-# endif
-	vector<ll> a(n, init);
-	SegTree seg(n, init);
-#endif
-	for (int i = 0; i < 5*n; i++) {
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll v = util::randint();
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-			if (v == 0) v = 1;
-# endif
-#endif
-			for (int j = l; j < r; j++) {
-#ifndef SEGTREE_MAX
-				a[j] = v;
-#else
-				a[j] += v;
-#endif
-			}
-			seg.update(l, r, v);
-		}
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-			ll comp = 0;
-# else
-			ll comp = numeric_limits<ll>::min();
-# endif
-#else
-			ll comp = numeric_limits<ll>::max();
-#endif
-			for (int j = l; j < r; j++) {
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-				comp += a[j];
-# else
-				comp = max(comp, a[j]);
-# endif
-#else
-				if (comp >= 0 && comp > a[j]) comp = a[j];
-#endif
-			}
-			assert(seg.query(l, r) == comp);
-		}
-#ifdef SEGTREE_MAX
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll bound = util::randint();
-			int found = -1;
-			for (int j = l; j < r; j++) {
-				if (a[j] >= bound) {
-					found = j;
-					break;
-				}
-			}
-			assert(seg.lower_bound(l, r, bound) == found);
-		}
-#endif
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-	{
-#ifndef SEGTREE_INIT_DEFAULT
-		vector<ll> a;
-		SegTree seg(a);
-#else
-		SegTree seg(0);
-#endif
-		seg.update(0, 0, util::randint());
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-		assert(seg.query(0, 0) == 0);
-# else
-		assert(seg.query(0, 0) == numeric_limits<ll>::min());
-# endif
-#else
-		assert(seg.query(0, 0) == numeric_limits<ll>::max());
-#endif
-	}
-}
diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
deleted file mode 100644
index 08927a2..0000000
--- a/datastructures/test/monotonicConvexHull.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#define sz(X) ((int)size(X))
-#include "../monotonicConvexHull.cpp"
-
-int main() {
-	{
-		Envelope env;
-		env.add(10, 0);
-		assert(env.query(0) == 0);
-		assert(env.query(1) == 10);
-		env.add(8, 5);
-		assert(env.query(1) == 10);
-		assert(env.query(2) == 20);
-		assert(env.query(3) == 29);
-		env.add(7, 10);
-		assert(env.query(10) == 80);
-		env.add(0, 0);
-		assert(env.query(11) == 0);
-	}
-
-	{
-		Envelope env;
-		env.add(1, 0);
-		env.add(0, 10);
-		env.add(-1, 10);
-		assert(env.query(7) == 3);
-	}
-}
diff --git a/datastructures/test/persistent.cpp b/datastructures/test/persistent.cpp
deleted file mode 100644
index 5e5f864..0000000
--- a/datastructures/test/persistent.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#define all(X) begin(X), end(X)
-#include "../persistent.cpp"
-
-int main() {
-	int time = 0;
-	persistent<int> p(time, 0);
-	p.set(1);
-	int t1 = time;
-	p.set(2);
-	assert(p.get(t1) == 1);
-}
diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk
deleted file mode 100644
index e863d4e..0000000
--- a/datastructures/test/segmentTree.awk
+++ /dev/null
@@ -1,74 +0,0 @@
-
-/Neutral element for combine/ {
-	print "#ifndef SEGTREE_MUL"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print
-	print "# else"
-	tmp = $0
-	sub(/0/, "numeric_limits<ll>::max()", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/0/, "1")
-	print
-	print "#endif"
-	next
-}
-
-/modify this \+ neutral/ {
-	print "#ifndef SEGTREE_MUL"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print
-	print "# else"
-	tmp = $0
-	sub(/a \+ b/, "a < 0 ? a : min(a, b)", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/a \+ b/, "a*b % MOD")
-	print
-	print "#endif"
-	next
-}
-
-/SegTree\(vector<T>& a\)/ {
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	print
-	getline
-	print
-	print "#else"
-	getline
-	sub(/\/\//, "")
-	print
-	getline
-	sub(/\/\//, "")
-	print
-	print "#endif"
-	next
-}
-
-/remove for range update/ {
-	print "#ifndef SEGTREE_RANGE_UPDATE"
-	print
-	getline
-	print
-	getline
-	print "\t\t}"
-	print "#endif"
-	print "\t}"
-	next
-}
-
-/void update/ {
-	print "#ifndef SEGTREE_RANGE_UPDATE"
-}
-
-/OR: range update/ {
-	print "#else"
-}
-
-/^\};$/ {
-	print "#endif"
-}
-
-{ print }
diff --git a/datastructures/test/segmentTree.cpp b/datastructures/test/segmentTree.cpp
deleted file mode 100644
index 44d99b6..0000000
--- a/datastructures/test/segmentTree.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
-#ifdef SEGTREE_MUL
-constexpr ll MOD = 1'000'000'007;
-#endif
-
-#include "segmentTree.tmp.cpp"
-
-void test(int n) {
-#ifndef SEGTREE_INIT_DEFAULT
-	vector<ll> a(n);
-	for (ll &x: a) x = util::randint();
-	SegTree seg(a);
-#else
-	ll init = util::randint();
-# ifdef SEGTREE_FIRST_NEG
-	init = abs(init);
-# endif
-	vector<ll> a(n, init);
-	SegTree seg(n, init);
-#endif
-	for (int i = 0; i < 5*n; i++) {
-		{
-#ifndef SEGTREE_RANGE_UPDATE
-			int j = util::randint(n);
-			ll v = util::randint();
-			a[j] = v;
-			seg.update(j, v);
-#else
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll v = util::randint();
-			for (int j = l; j < r; j++) {
-# ifndef SEGTREE_MUL
-				a[j] += v;
-# else
-				a[j] = a[j]*v % MOD;
-# endif
-			}
-			seg.modify(l, r, v);
-#endif
-		}
-		{
-#ifndef SEGTREE_RANGE_UPDATE
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-			ll comp = 0;
-#  else
-			ll comp = numeric_limits<ll>::max();
-#  endif
-# else
-			ll comp = 1;
-# endif
-			for (int j = l; j < r; j++) {
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-				comp += a[j];
-#  else
-				if (comp >= 0 && comp > a[j]) comp = a[j];
-#  endif
-# else
-				comp = comp * a[j] % MOD;
-# endif
-			}
-			assert(seg.query(l, r) == comp);
-#else
-			int j = util::randint(n);
-			assert(seg.query(j) == a[j]);
-#endif
-		}
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-	{
-#ifndef SEGTREE_INIT_DEFAULT
-		vector<ll> a;
-		SegTree seg(a);
-#else
-		SegTree seg(0);
-#endif
-#ifndef SEGTREE_RANGE_UPDATE
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-		assert(seg.query(0, 0) == 0);
-#  else
-		assert(seg.query(0, 0) == numeric_limits<ll>::max());
-#  endif
-# else
-		assert(seg.query(0, 0) == 1);
-# endif
-#else
-		seg.modify(0, 0, util::randint());
-#endif
-	}
-}
diff --git a/datastructures/test/sparseTable.cpp b/datastructures/test/sparseTable.cpp
deleted file mode 100644
index 03ef548..0000000
--- a/datastructures/test/sparseTable.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTable.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	SparseTable st;
-	st.init(values);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n);
-		int r = util::randint(n);
-		if (l > r) swap(l, r);
-		r++;
-		assert(
-			values[st.queryIdempotent(l, r)]
-			==
-			*min_element(values.begin()+l, values.begin()+r)
-		);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}
diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp
deleted file mode 100644
index 7ef6483..0000000
--- a/datastructures/test/sparseTableDisjoint.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTableDisjoint.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	DisjointST st;
-	st.init(values);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n);
-		int r = util::randint(n);
-		if (l > r) swap(l, r);
-		r++;
-		assert(
-			st.query(l, r)
-			==
-			accumulate(values.begin()+l, values.begin()+r, 0ll)
-		);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}
diff --git a/datastructures/test/treap2.cpp b/datastructures/test/treap2.cpp
deleted file mode 100644
index 1a435d3..0000000
--- a/datastructures/test/treap2.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#include "../treap2.cpp"
-
-void test(int n) {
-	Treap treap;
-	vector<ll> dumb;
-	for (int i = 0; i < n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		int j = util::randint(ssize(dumb) + 1);
-		ll x = util::randint();
-		treap.insert(j, x);
-		dumb.insert(begin(dumb) + j, x);
-	}
-	for (int i = 0; i < 5*n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		{
-			int j = util::randint(ssize(dumb));
-			treap.remove(j);
-			dumb.erase(begin(dumb) + j);
-		}
-		{
-			int j = util::randint(ssize(dumb) + 1);
-			ll x = util::randint();
-			treap.insert(j, x);
-			dumb.insert(begin(dumb) + j, x);
-		}
-	}
-	for (int i = 0; i < n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		int j = util::randint(ssize(dumb));
-		treap.remove(j);
-		dumb.erase(begin(dumb) + j);
-	}
-	assert(treap.root < 0);
-	assert(empty(dumb));
-}
-
-int main() {
-	test(1000);
-	test(1);
-	test(0);
-}
diff --git a/datastructures/test/waveletTree.cpp b/datastructures/test/waveletTree.cpp
deleted file mode 100644
index c5da1d2..0000000
--- a/datastructures/test/waveletTree.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-#include "../waveletTree.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	vector<ll> backup = values;
-	WaveletTree wave(values);
-	assert(values == backup);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n+1);
-		int r = util::randint(n+1);
-		if (l > r) swap(l, r);
-		ll bound = util::randint();
-		int res = 0;
-		for (ll x: values | views::take(r) | views::drop(l)) {
-			if (x < bound) res++;
-		}
-		assert(wave.countSmaller(l, r, bound) == res);
-	}
-	for (int i = 0; 5*i < n; i++) {
-		int l = util::randint(n);
-		int m = util::randint(n);
-		int r = util::randint(n);
-		if (l > m) swap(l, m);
-		if (m > r) swap(m, r);
-		if (l > m) swap(l, m);
-		r++;
-		int k = m-l;
-		vector<ll> part(values.begin()+l, values.begin()+r);
-		ranges::nth_element(part, part.begin() + k);
-		assert(wave.kth(l, r, k) == part[k]);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}
diff --git a/datastructures/treap.cpp b/datastructures/treap.cpp
deleted file mode 100644
index c96e36a..0000000
--- a/datastructures/treap.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
-
-vector<node> treap;
-
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
-
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
-
-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;
-}}
-
-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;
-}}
-
-//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 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);
-}}
-
-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);
-	}
-	return root;
-}
diff --git a/datastructures/treap2.cpp b/datastructures/treap2.cpp
deleted file mode 100644
index e40da0d..0000000
--- a/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, ssize(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/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
deleted file mode 100644
index 68eef86..0000000
--- a/datastructures/unionFind.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-// unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -size
-vector<int> unions;
-
-void init(int n) { //Initialisieren
-	unions.assign(n, -1);
-}
-
-int findSet(int n) { // Pfadkompression
-	if (unions[n] < 0) return n;
-	return unions[n] = findSet(unions[n]);
-}
-
-void linkSets(int a, int b) { // Union by size.
-	if (unions[b] > unions[a]) swap(a, b);
-	unions[b] += unions[a];
-	unions[a] = b;
-}
-
-void unionSets(int a, int b) { // Diese Funktion aufrufen.
-	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
-}
-
-int size(int a) {
-	return -unions[findSet(a)];
-}
diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp
deleted file mode 100644
index d1b9162..0000000
--- a/datastructures/unionFind2.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-// unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -size
-vector<int> unions;
-
-init(int n) {
-	unions.assign(n, -1);
-}
-
-int findSet(int i) {
-	if (unions[i] < 0) return i;
-	return unions[i] = findSet(unions[i]);
-}
-
-void linkSets(int a, int b) { // Union by size.
-	if (unions[b] > unions[a]) swap(a, b);
-	unions[b] += unions[a];
-	unions[a] = b;
-}
-
-void unionSets(int a, int b) {
-	if (findSet(a) != findSet(b)) linkSets(findSet(a),findSet(b));
-}
-
-void getSize(int i) {
-	return -unions[findSet(i)];
-}
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp
deleted file mode 100644
index 95ff207..0000000
--- a/datastructures/waveletTree.cpp
+++ /dev/null
@@ -1,32 +0,0 @@
-struct WaveletTree {
-	unique_ptr<WaveletTree> ln, rn;
-	vector<int> b = {0};
-	ll lo, hi;
-
-	WaveletTree(auto in) : lo(*ranges::min_element(in)),
-	                       hi(*ranges::max_element(in) + 1) {
-		ll mid = (lo + hi) / 2;
-		auto f = [&](ll x) { return x < mid; };
-		for (ll x: in) b.push_back(b.back() + f(x));
-		if (lo + 1 >= hi) return;
-		auto right = ranges::stable_partition(in, f);
-		ln = make_unique<WaveletTree>(
-		  ranges::subrange(begin(in), begin(right)));
-		rn = make_unique<WaveletTree>(right);
-	}
-
-	ll kth(int l, int r, int k) {
-		if (l >= r || k >= r - l) return -1;
-		if (lo + 1 >= hi) return lo;
-		int inLeft = b[r] - b[l];
-		if (k < inLeft) return ln->kth(b[l], b[r], k);
-		else return rn->kth(l-b[l], r-b[r], k-inLeft);
-	}
-
-	int countSmaller(int l, int r, ll k) {
-		if (l >= r || k <= lo) return 0;
-		if (hi <= k) return r - l;
-		return ln->countSmaller(b[l], b[r], k) +
-		       rn->countSmaller(l-b[l], r-b[r], k);
-	}
-};