merge mzuenni changes

9 files changed, 94 insertions, 173 deletions

diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index a0eea64..4bbe507 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -52,7 +52,7 @@
 		\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)}
 		\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
 	\end{methods}
-	\sourcecode{datastructures/treap2.cpp}
+	\sourcecode{datastructures/treap.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Range Minimum Query}
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 2bd67a6..7148e31 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
 struct Line {
-	mutable ll m, b, p;
+	mutable ll m, c, p;
 	bool operator<(const Line& o) const {return m < o.m;}
 	bool operator<(ll x) const {return p < x;}
 };
 
-struct HullDynamic : multiset<Line, less<>> {
-	// (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);}
+struct HullDynamic : multiset<Line, less<>> { // max über Geraden
+	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
+	ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
-		else x->p = div(y->b - x->b, x->m - y->m);
+		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
 
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
+	void add(ll m, ll c) {
+		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
 			--x;
@@ -29,6 +29,6 @@ struct HullDynamic : multiset<Line, less<>> {
 
 	ll query(ll x) {
 		auto l = *lower_bound(x);
-		return l.m * x + l.b;
+		return l.m * x + l.c;
 	}
 };
diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index f66778e..1318ca7 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -8,13 +8,13 @@ struct Fun { // Default: Linear function. Change as needed.
 
 // Default: Computes min. Change lines with comment for max.
 struct Lichao {
-	static constexpr Fun id = {0, inf}; // {0, -inf}
+	static constexpr Fun id = {0, INF}; // {0, -INF}
 	int n, cap;
 	vector<Fun> seg;
-	Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
+	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
 	
 	void _insert(Fun f, int l, int r, int i) {
-		while (i < 2*cap){
+		while (i < 2 * cap) {
 			int m = (l+r)/2;
 			if (m >= n) {r = m; i = 2*i; continue;}
 			Fun &g = seg[i];
@@ -26,7 +26,7 @@ struct Lichao {
 
 	void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
 		if (l <= a && b <= r) _insert(f, a, b, i);
-		else if (a < r && l < b){
+		else if (a < r && l < b) {
 			int m = (a+b)/2;
 			_segmentInsert(f, l, r, a, m, 2*i);
 			_segmentInsert(f, l, r, m, b, 2*i+1);
@@ -36,7 +36,7 @@ struct Lichao {
 	}
 
 	ll _query(int x) {
-		ll ans = inf; // -inf
+		ll ans = INF; // -INF
 		for (int i = x + cap; i > 0; i /= 2) {
 			ans = min(ans, seg[i](x)); // max
 		}
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index e7b9b3e..2bdeccf 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -16,7 +16,7 @@ struct Envelope {
 			ls.pop_back();
 		}
 		ls.push_back({m, b});
-		ptr = min(ptr, sz(ls) - 1);
+		ptr = min(ptr, (int)sz(ls) - 1);
 	}
 
 	ll query(ll x) {
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index d00b635..734bf91 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -15,10 +15,10 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 T.order_of_key(x); // number of elements strictly less than x
 auto it = T.find_by_order(k); // k-th element
 
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
 template<typename T> struct chash {
-	static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
 	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
+		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
 template<typename K, typename V>
 using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 4093cdc..f26680d 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -4,15 +4,15 @@ struct persistent {
 	vector<pair<int, T>> data;

 

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

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

+		: time(time), data(1, {2*time, value}) {}

 	

 	T get(int t) {

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

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

 	}

 	

 	int set(T value) {

-		time += 2;

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

+		time++;

+		data.push_back({2*time, value});

 		return time;

 	}

 };

diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp
index 60d8b17..8326700 100644
--- a/content/datastructures/persistentArray.cpp
+++ b/content/datastructures/persistentArray.cpp
@@ -10,8 +10,8 @@ struct persistentArray {
 	T get(int p, int t) {return data[p].get(t);}

 

 	int set(int p, T value) {

-		mods.push_back({p, time});

-		return data[p].set(value);

+		mods.push_back({p, data[p].set(value)});

+		return mods.back().second;

 	}

 

 	void reset(int t) {

diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c96e36a..c5a60e9 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -1,79 +1,79 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
+mt19937 rng(0xc4bd5dad);
+struct Treap {
+	struct Node {
+		ll val;
+		int prio, size = 1, l = -1, r = -1;
+		Node(ll x) : val(x), prio(rng()) {}
+	};
 
-vector<node> treap;
+	vector<Node> treap;
+	int root = -1;
 
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
+	int getSize(int v) {
+		return v < 0 ? 0 : treap[v].size;
+	}
 
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
+	void upd(int v) {
+		if (v < 0) return;
+		auto& V = treap[v];
+		V.size = 1 + getSize(V.l) + getSize(V.r);
+		// Update Node Code
+	}
 
-pair<int, int> split(int root, int minKeyRight) {
-	if (root < 0) return {-1, -1};
-	if (treap[root].key >= minKeyRight) {
-		auto leftSplit = split(treap[root].left, minKeyRight);
-		treap[root].left = leftSplit.second;
-		update(root);
-		leftSplit.second = root;
-		return leftSplit;
-	} else {
-		auto rightSplit = split(treap[root].right, minKeyRight);
-		treap[root].right = rightSplit.first;
-		update(root);
-		rightSplit.first = root;
-		return rightSplit;
-}}
+	void push(int v) {
+		if (v < 0) return;
+		//auto& V = treap[v];
+		//if (V.lazy) {
+		//	Lazy Propagation Code
+		//	if (V.l >= 0) treap[V.l].lazy = true;
+		//	if (V.r >= 0) treap[V.r].lazy = true;
+		//	V.lazy = false;
+		//}
+	}
 
-int merge (int left, int right) {
-	if (left < 0) return right;
-	if (right < 0) return left;
-	if (treap[left].prio < treap[right].prio) { //min priority heap
-		treap[left].right = merge(treap[left].right, right);
-		update(left);
-		return left;
-	} else {
-		treap[right].left = merge(left, treap[right].left);
-		update(right);
-		return right;
-}}
+	pair<int, int> split(int v, int k) {
+		if (v < 0) return {-1, -1};
+		auto& V = treap[v];
+		push(v);
+		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+			auto [left, right] = split(V.l, k);
+			V.l = right;
+			upd(v);
+			return {left, v};
+		} else {
+			// and only "k"
+			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+			V.r = left;
+			upd(v);
+			return {v, right};
+	}}
 
-//insert values with high priority first
-int insert(int root, int key, int prio) {
-	int next = sz(treap);
-	treap.emplace_back(key, prio);
-	auto t = split(root, key);
-	//returns new root
-	return merge(merge(t.first, next), t.second);
-}
+	int merge(int left, int right) {
+		if (left < 0) return right;
+		if (right < 0) return left;
+		if (treap[left].prio < treap[right].prio) {
+			push(left);
+			treap[left].r = merge(treap[left].r, right);
+			upd(left);
+			return left;
+		} else {
+			push(right);
+			treap[right].l = merge(left, treap[right].l);
+			upd(right);
+			return right;
+	}}
 
-int remove(int root, int key) {
-	if (root < 0) return -1;
-	if (key < treap[root].key) {
-		treap[root].left = remove(treap[root].left, key);
-		update(root);
-		return root;
-	} else if (key > treap[root].key) {
-		treap[root].right = remove(treap[root].right, key);
-		update(root);
-		return root;
-	} else { //check prio?
-		return merge(treap[root].left, treap[root].right);
-}}
+	void insert(int i, ll val) { // and i = val
+		auto [left, right] = split(root, i);
+		treap.emplace_back(val);
+		left = merge(left, sz(treap) - 1);
+		root = merge(left, right);
+	}
 
-int kth(int root, int k) {
-	if (root < 0) return -1;
-	int leftSize = getSize(treap[root].left);
-	if (k < leftSize) return kth(treap[root].left, k);
-	else if (k > leftSize) {
-		return kth(treap[root].right, k - 1 - leftSize);
+	void remove(int i, int count = 1) {
+		auto [left, t_right] = split(root, i);
+		auto [middle, right] = split(t_right, count);
+		root = merge(left, right);
 	}
-	return root;
-}
+	// for query use remove and read middle BEFORE remerging
+};
diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp
deleted file mode 100644
index e40da0d..0000000
--- a/content/datastructures/treap2.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-mt19937 rng(0xc4bd5dad);
-struct Treap {
-	struct Node {
-		ll val;
-		int prio, size = 1, l = -1, r = -1;
-		Node(ll x): val(x), prio(rng()) {}
-	};
-
-	vector<Node> treap;
-	int root = -1;
-
-	int getSize(int v) {
-		return v < 0 ? 0 : treap[v].size;
-	}
-
-	void upd(int v) {
-		if (v < 0) return;
-		auto &V = treap[v];
-		V.size = 1 + getSize(V.l) + getSize(V.r);
-		// Update Node Code
-	}
-
-	void push(int v) {
-		if (v < 0) return;
-		//auto &V = treap[v];
-		//if (V.lazy) {
-		//	Lazy Propagation Code
-		//	if (V.l >= 0) treap[V.l].lazy = true;
-		//	if (V.r >= 0) treap[V.r].lazy = true;
-		//	V.lazy = false;
-		//}
-	}
-
-	pair<int, int> split(int v, int k) {
-		if (v < 0) return {-1, -1};
-		auto &V = treap[v];
-		push(v);
-		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
-			auto [left, right] = split(V.l, k);
-			V.l = right;
-			upd(v);
-			return {left, v};
-		} else {
-			// and only "k"
-			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
-			V.r = left;
-			upd(v);
-			return {v, right};
-	}}
-
-	int merge(int left, int right) {
-		if (left < 0) return right;
-		if (right < 0) return left;
-		if (treap[left].prio < treap[right].prio) {
-			push(left);
-			treap[left].r = merge(treap[left].r, right);
-			upd(left);
-			return left;
-		} else {
-			push(right);
-			treap[right].l = merge(left, treap[right].l);
-			upd(right);
-			return right;
-	}}
-
-	void insert(int i, ll val) { // and i = val
-		auto [left, right] = split(root, i);
-		treap.emplace_back(val);
-		left = merge(left, 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
-};