Test (#4)

* update

* moved content in subdir

* rename file

* add test setup

* add test setup

* add github action

* automaticly test all cpp files

* timeout after 10s

* setulimit and dont zero memory

* test build pdf

* install latexmk

* update

* update

* ngerman

* fonts

* removed old code

* add first test

* added tests

* test in sorted order

* more tests

* simplified test

* more tests

* fix suffix tree

* fixes and improvements

* done ust lst directly

* fix swap

* add links to pdf

* fix constants

* add primorial

* add comment

* various improvements

* more tests

* added missing stuf

* more tests

* fix tests

* more tests

* more tests

* more tests

* fix recursion?

* test trie

* more tests

* only use python temporarily for listings

* only use python temporarily for listings

* more tests

* fix longestCommonSubstring

* more tests

* more tests

* made code more similiar

* fix?

* more tests

* more tests

* more tests

* add ahoCorasick test + limit 4GB stack size

* more tests

* fix test

* add additional test

* more tests

* more tests

* fix?

* better fix

* fix virtual tree

* more tests

* more tests

* recursive closest pair

* more tests

* decrease limit

* new tests

* more tests

* fix name

* more tests

* add test

* new test

* more tests

* more tests

* more tests

* more tests

* new test and content

* new code

* new code

* larger tests

* fix and test

* new test

* new test

* update pdf

* remove comments

* new test

* more tests

* more testcases

* more tests

* increased limit

* more tests

* more tests

* more tests

* new tests

* more tests

* shortened code

* new test

* add basic tests for bigint

* more tests

* removed old files

* new test

* ignore some files

* more auto more ccw

* fix test

* more tests

* fix

* new tests

* more tests

* more tests

* stronger test

* actually verify delaunay...

* more tests

* fix header

* more tests

* run tests parallel?

* test parralel?

* add --missing

* separate workflows

* test

* is the pdf checked?

* separate workflows

* fix workflow

* more workflows

---------

Co-authored-by: Yidi <noob999noob999@gmail.com>

27 files changed, 0 insertions, 1050 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/RMQ.cpp b/datastructures/RMQ.cpp
deleted file mode 100644
index 401cca4..0000000
--- a/datastructures/RMQ.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-vector<int> values;
-vector<vector<int>> rmq;
-
-int select(int a, int b) {
-	return values[a] <= values[b] ? a : b;
-}
-
-void build() {
-	for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) {
-		for(int l = 0; l + s <= sz(values); l++) {
-			if(i == 0) rmq[0][l] = l;
-			else {
-				int r = l + ss;
-				rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]);
-}}}}
-
-void init(const vector<int>& v) {
-	values = v;
-	rmq = vector<vector<int>>(__lg(sz(values))+1, vector<int>(sz(values)));
-	build();
-}
-
-int query(int l, int r) {
-	if(l >= r) return l;
-	int s = __lg(r-l); r = r - (1 << s);
-	return select(rmq[s][l],rmq[s][r]);
-}
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 d35dfb0..0000000
--- a/datastructures/datastructures.tex
+++ /dev/null
@@ -1,136 +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{Constructor}{baut den Baum auf}{n\*\log(n)}
-		\method{kth}{sort $[l, r)[k]$}{\log(n)}
-		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
-	\end{methods}
-	\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 >= $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}{STL-Bitset}
-	\sourcecode{datastructures/bitset.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Link-Cut-Tree}
-	\begin{methods}
-		\method{Constructor}{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}
-\clearpage
-
-\begin{algorithm}{Lichao}
-    \sourcecode{datastructures/lichao.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Policy Based Data Structures}
-    \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}!
-	\sourcecode{datastructures/stlPriorityQueue.cpp}
-	\columnbreak
-	\sourcecode{datastructures/pbds.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Lower/Upper 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.
-	\sourcecode{datastructures/monotonicConvexHull.cpp}
-	\sourcecode{datastructures/dynamicConvexHull.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}
-\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]{Range Minimum Query}
-	\begin{methods}
-		\method{init}{baut Struktur auf}{n\*\log(n)}
-		\method{query}{Index des Minimums in [l, r)}{1}
-	\end{methods}
-	\sourcecode{datastructures/RMQ.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 d669847..0000000
--- a/datastructures/dynamicConvexHull.cpp
+++ /dev/null
@@ -1,36 +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--;
-			if (isect(x, next(x))) {
-				erase(next(x));
-				isect(x, 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 cac3cf8..0000000
--- a/datastructures/fenwickTree.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-vector<ll> tree;
-
-void update(int i, ll val) {
-	for (i++; i < sz(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++; i > 0; i -= (i & (-i))) sum += tree[i];
-	return sum;
-}
diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp
deleted file mode 100644
index ff87e2e..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 < sz(add); tl += tl&(-tl))
-		add[tl] += val, mul[tl] -= val * l;
-	for (int tr = r + 1; tr < sz(add); tr += tr&(-tr))
-		add[tr] -= val, mul[tr] += val * r;
-}
-
-void init(vector<ll>& v) {
-	mul.assign(sz(v) + 1,0);
-	add.assign(sz(v) + 1,0);
-	for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]);
-}
-
-ll prefix_sum (int i) {
-	ll res = 0; i++;
-	for (int ti = i; ti > 0; ti -= ti&(-ti))
-		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 0fe7bbe..0000000
--- a/datastructures/lazyPropagation.cpp
+++ /dev/null
@@ -1,83 +0,0 @@
-struct SegTree {
-	using T = ll; using U = ll;
-	int n, h;
-	static constexpr T E = 0; // Neutral element for combine
-	static constexpr U UF = 0; // Unused value by updates
-	vector<T> tree; vector<U> lazy;
-	vector<ll> k; // size of segments (optional)
-
-	SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E),
-	//SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def),
-			h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) {
-		copy(all(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 - 1);
-		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) apply(l++, val);
-			if (r&1) apply(--r, val);
-		}
-		build(l0), build(r0 - 1);
-	}
-
-	T query(int l, int r) {
-		l += n, r += n;
-		push(l), push(r - 1);
-		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 44bff83..0000000
--- a/datastructures/monotonicConvexHull.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-// 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;}
-};
-
-vector<Line> ls;
-int 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);
-}
-
-void add(ll m, ll b) { // Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
-		ls.pop_back();
-	}
-	ls.push_back({m, b});
-	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++;
-	return ls[ptr](x);
-}
\ No newline at end of file
diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp
deleted file mode 100644
index c2b44cc..0000000
--- a/datastructures/pbds.cpp
+++ /dev/null
@@ -1,18 +0,0 @@
-#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
-// *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 0a65a79..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), {t+1, {}}))->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 79c6cae..0000000
--- a/datastructures/segmentTree.cpp
+++ /dev/null
@@ -1,42 +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(sz(a)), tree(2 * n) {
-	//SegTree(int size, T val = E) : n(size), tree(2 * n, val) {
-		copy(all(a), tree.begin() + n);
-		for (int i = n - 1; i > 0; i--) { // remove for range update
-			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
-	}}
-
-	ll 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 63cce48..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 31e9025..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->at(i));
-				for (int i = min(n, c); i > c - l; i--)
-					dst[h][i - 1] = combine(vec->at(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/stlHashMap.cpp b/datastructures/stlHashMap.cpp
deleted file mode 100644
index b107dde..0000000
--- a/datastructures/stlHashMap.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-#include <ext/pb_ds/assoc_container.hpp>
-using namespace __gnu_pbds;
-
-template<typename T>
-struct betterHash {
-	size_t operator()(T o) const {
-		size_t h = hash<T>()(o) ^ 42394245; //random value
-		h = ((h >> 16) ^ h) * 0x45d9f3b;
-		h = ((h >> 16) ^ h) * 0x45d9f3b;
-		h = ((h >> 16) ^ h);
-		return h;
-}};
-
-template<typename K, typename V, typename H = betterHash<K>>
-using hashMap = gp_hash_table<K, V, H>;
-template<typename K, typename H = betterHash<K>>
-using hashSet = gp_hash_table<K, null_type, H>;
diff --git a/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp
deleted file mode 100644
index 4e439f8..0000000
--- a/datastructures/stlPQ.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-#include <ext/pb_ds/priority_queue.hpp>
-template<typename T>
-// greater<T> für Min-Queue
-using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>;
-
-int main() {
-	priorityQueue<int> pq;
-	auto it = pq.push(5);   // O(1)
-	pq.push(7);
-	pq.pop();               // O(log n) amortisiert
-	pq.modify(it, 6);       // O(log n) amortisiert
-	pq.erase(it);           // O(log n) amortisiert
-	priorityQueue<int> pq2;
-	pq.join(pq2);           // O(1)
-}
diff --git a/datastructures/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp
deleted file mode 100644
index 32b2455..0000000
--- a/datastructures/stlPriorityQueue.cpp
+++ /dev/null
@@ -1,8 +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);
-pq.modify(it, 6);
-pq.join(pq2);
-// push, join are O(1), pop, modify, erase O(log n) amortized
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/stlTree.cpp b/datastructures/stlTree.cpp
deleted file mode 100644
index fbb68b9..0000000
--- a/datastructures/stlTree.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-#include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
-using namespace std; using namespace __gnu_pbds;
-template<typename T>
-using Tree = tree<T, null_type, less<T>, rb_tree_tag,
-                  tree_order_statistics_node_update>;
-
-int main() {
-	Tree<int> X;
-	for (int i : {1, 2, 4, 8, 16}) X.insert(i);
-	*X.find_by_order(3); // => 8
-	X.order_of_key(10);  // => 4 = min i, mit X[i] >= 10
-}
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 10168ca..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, 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/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 5362c4d..0000000
--- a/datastructures/unionFind2.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-vector<int> uf;
-
-init(int N) {
-	uf.assign(N,-1); //-1 indicates that every subset has size 1
-}
-
-int findSet(int i) {
-	if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root
-	uf[i] = findSet(uf[i]); //Path-Compression
-	return uf[i];
-}
-
-void linkSets(int i, int j) {
-	//Take |uf[i]|, where i must be a root, to get the size
-	//of the subset
-	if(abs(uf[i]) < abs(uf[j])) { //Union-by-size.
-		uf[j] += uf[i]; uf[i] = j;
-	} else {
-		uf[i] += uf[j]; uf[j] = i;
-	}
-}
-
-void unionSets(int i, int j) {
-	if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j));
-}
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp
deleted file mode 100644
index 476658e..0000000
--- a/datastructures/waveletTree.cpp
+++ /dev/null
@@ -1,40 +0,0 @@
-struct WaveletTree {
-	using it = vector<ll>::iterator;
-	WaveletTree *ln = nullptr, *rn = nullptr;
-	vector<int> b = {0};
-	ll lo, hi;
-
-	WaveletTree(vector<ll> in) : WaveletTree(all(in)) {}
-
-	WaveletTree(it from, it to) : // call above one
-		lo(*min_element(from, to)), hi(*max_element(from, to) + 1) {
-		ll mid = (lo + hi) / 2;
-		auto f = [&](ll x) {return x < mid;};
-		for (it c = from; c != to; c++) {
-			b.push_back(b.back() + f(*c));
-		}
-		if (lo + 1 >= hi) return;
-		it pivot = stable_partition(from, to, f);
-		ln = new WaveletTree(from, pivot);
-		rn = new WaveletTree(pivot, to);
-	}
-
-	// kth element in sort[l, r) all 0-indexed
-	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);
-	}
-
-	// count elements in[l, r) smaller than k
-	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);
-	}
-
-	~WaveletTree() {delete ln; delete rn;}
-};