merge

5 files changed, 97 insertions, 76 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 4139219..1ccefaa 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -14,6 +14,15 @@
 	\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}
+
 \begin{algorithm}{Fenwick Tree}
 	\begin{methods}
 		\method{init}{baut den Baum auf}{n\*\log(n)}
@@ -29,11 +38,11 @@
 	\end{methods}
 	\sourcecode{datastructures/fenwickTree2.cpp}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
 	\sourcecode{datastructures/stlRope.cpp}
 \end{algorithm}
+\columnbreak
 
 \begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
 	\begin{methods}
@@ -54,15 +63,6 @@
 	\sourcecode{datastructures/sparseTable.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}
-
 \begin{algorithm}{STL-Bitset}
 	\sourcecode{datastructures/bitset.cpp}
 \end{algorithm}
@@ -81,6 +81,23 @@
 \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}
@@ -90,13 +107,7 @@
 	\end{methods}
 	\sourcecode{datastructures/unionFind.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}
-	\columnbreak
-	\sourcecode{datastructures/dynamicConvexHull.cpp}
-\end{algorithm}
+\columnbreak
 
 \begin{algorithm}{Persistent}
 	\begin{methods}
@@ -108,22 +119,6 @@
 	\sourcecode{datastructures/persistentArray.cpp}
 \end{algorithm}
 
-\begin{algorithm}{STL-Tree}
-	\sourcecode{datastructures/stlTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL Priority Queue}
-	Nicht notwendig, wenn Smaller-Larger-Optimization greift.
-	\sourcecode{datastructures/stlPQ.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL HashMap}
-	3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
-	\sourcecode{datastructures/stlHashMap.cpp}
-\end{algorithm}
-
-
-
 \begin{algorithm}[optional]{Range Minimum Query}
 	\begin{methods}
 		\method{init}{baut Struktur auf}{n\*\log(n)}
@@ -138,4 +133,3 @@
 	\end{methods}
 	\sourcecode{datastructures/firstUnused.cpp}
 \end{algorithm}
-
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp
index 7af1a6a..0fe7bbe 100644
--- a/datastructures/lazyPropagation.cpp
+++ b/datastructures/lazyPropagation.cpp
@@ -65,13 +65,12 @@ struct SegTree {
 	ll lower_bound(int l, int r, T x) {
 		l += n, r += n;
 		push(l), push(r - 1);
-		vector<int> a, st;
+		int a[64] = {}, lp = 0, rp = 64;
 		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) a.push_back(l++);
-			if (r&1) st.push_back(--r);
+			if (l&1) a[lp++] = l++;
+			if (r&1) a[--rp] = --r;
 		}
-		a.insert(a.end(), st.rbegin(), st.rend());
-		for (int i : a) if (tree[i] >= x) { // Modify this
+		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
diff --git a/datastructures/lichao.cpp b/datastructures/lichao.cpp
index e12d243..f66778e 100644
--- a/datastructures/lichao.cpp
+++ b/datastructures/lichao.cpp
@@ -1,44 +1,46 @@
-vector<ll> xs; // IMPORTANT: Initialize before constructing Lichao!
-int findX(int i) {return distance(xs.begin(), lower_bound(all(xs), i));}
+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 it to needed function type. 
-    ll m, c;
-    ll operator()(int x) {return m*xs[x] + c;}
+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);}
+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);
-    }
+	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));}
+	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/pbds.cpp b/datastructures/pbds.cpp
new file mode 100644
index 0000000..c2b44cc
--- /dev/null
+++ b/datastructures/pbds.cpp
@@ -0,0 +1,18 @@
+#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/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp
new file mode 100644
index 0000000..32b2455
--- /dev/null
+++ b/datastructures/stlPriorityQueue.cpp
@@ -0,0 +1,8 @@
+#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