diff options
Diffstat (limited to 'content/datastructures')
| -rw-r--r-- | content/datastructures/datastructures.tex | 57 | ||||
| -rw-r--r-- | content/datastructures/dynamicConvexHull.cpp | 18 | ||||
| -rw-r--r-- | content/datastructures/fenwickTree.cpp | 4 | ||||
| -rw-r--r-- | content/datastructures/fenwickTree2.cpp | 16 | ||||
| -rw-r--r-- | content/datastructures/lazyPropagation.cpp | 37 | ||||
| -rw-r--r-- | content/datastructures/lichao.cpp | 17 | ||||
| -rw-r--r-- | content/datastructures/monotonicConvexHull.cpp | 42 | ||||
| -rw-r--r-- | content/datastructures/pbds.cpp | 16 | ||||
| -rw-r--r-- | content/datastructures/persistent.cpp | 36 | ||||
| -rw-r--r-- | content/datastructures/persistentArray.cpp | 48 | ||||
| -rw-r--r-- | content/datastructures/segmentTree.cpp | 9 | ||||
| -rw-r--r-- | content/datastructures/sparseTable.cpp | 10 | ||||
| -rw-r--r-- | content/datastructures/sparseTableDisjoint.cpp | 10 | ||||
| -rw-r--r-- | content/datastructures/stlHashMap.cpp | 17 | ||||
| -rw-r--r-- | content/datastructures/stlPriorityQueue.cpp | 8 | ||||
| -rw-r--r-- | content/datastructures/stlTree.cpp | 13 | ||||
| -rw-r--r-- | content/datastructures/treap.cpp | 2 | ||||
| -rw-r--r-- | content/datastructures/waveletTree.cpp | 26 |
18 files changed, 185 insertions, 201 deletions
diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex index c9f3d2a..c4bd312 100644 --- a/content/datastructures/datastructures.tex +++ b/content/datastructures/datastructures.tex @@ -10,7 +10,7 @@ \subsubsection{Lazy Propagation} Assignment modifications, sum queries \\ - \method{lower\_bound}{erster Index in $[l, r)$ $\geq$ x (erfordert max-combine)}{\log(n)} + \method{binary\_search}{kleinstes $x$ in $[l, r]$ mit $f(\text{query}(l, x))$ (monoton in $x$)}{\log(n)} \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} @@ -20,6 +20,8 @@ \method{kth}{sort $[l, r)[k]$}{\log(\Sigma)} \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)} \end{methods} + $\Sigma$ ist die Gr\"o\ss e des Eingabebereichs, d.h. + $\mathit{max} - \mathit{min}$. \sourcecode{datastructures/waveletTree.cpp} \end{algorithm} \columnbreak @@ -27,15 +29,15 @@ \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{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)$. $l\leq r$!}{\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} @@ -56,7 +58,7 @@ \begin{algorithm}{Range Minimum Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} - \method{queryIdempotent}{Index des Minimums in $[l, r)$. $l<r$!}{1} + \method{query}{Index des Minimums in $[l, r)$}{1} \end{methods} \begin{itemize} \item \code{better}-Funktion muss idempotent sein! @@ -64,6 +66,14 @@ \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} @@ -80,30 +90,43 @@ \end{methods} \sourcecode{datastructures/LCT.cpp} \end{algorithm} -\clearpage +\columnbreak -\begin{algorithm}{Lichao} - \sourcecode{datastructures/lichao.cpp} +\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}{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{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)} \method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)} \end{methods} \sourcecode{datastructures/unionFind.cpp} diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 63e0e13..36ef6f5 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,15 +1,15 @@ struct Line { mutable ll m, c, p; - bool operator<(const Line& o) const {return m < o.m;} - bool operator<(ll x) const {return p < x;} + bool operator<(const Line& o) const { return m < o.m; } + bool operator<(ll x) const { return p < x; } }; 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);} + 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 (y == end()) { x->p = INF; return false; } 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; @@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden auto x = insert({m, c, 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)); - }} + --x; + while (isect(x, next(x))) erase(next(x)); + } while (x != begin() && prev(x)->p >= x->p) { - x--; + --x; isect(x, erase(next(x))); }} diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp index eb5cd73..7013613 100644 --- a/content/datastructures/fenwickTree.cpp +++ b/content/datastructures/fenwickTree.cpp @@ -1,7 +1,7 @@ vector<ll> tree; void update(int i, ll val) { - for (i++; i < sz(tree); i += i & -i) tree[i] += val; + for (i++; i < ssize(tree); i += i & -i) tree[i] += val; } void init(int n) { @@ -10,6 +10,6 @@ void init(int n) { ll prefix_sum(int i) { ll sum = 0; - for (i++; i > 0; i -= i & -i) sum += tree[i]; + for (; i > 0; i &= i-1) sum += tree[i]; return sum; } diff --git a/content/datastructures/fenwickTree2.cpp b/content/datastructures/fenwickTree2.cpp index 9384e3c..7fcdbb9 100644 --- a/content/datastructures/fenwickTree2.cpp +++ b/content/datastructures/fenwickTree2.cpp @@ -1,21 +1,21 @@ vector<ll> add, mul; void update(int l, int r, ll val) { - for (int tl = l + 1; tl < sz(add); tl += tl & -tl) + for (int tl = l + 1; tl < ssize(add); tl += tl & -tl) add[tl] += val, mul[tl] -= val * l; - for (int tr = r + 1; tr < sz(add); tr += tr & -tr) + 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(sz(v) + 1, 0); - add.assign(sz(v) + 1, 0); - for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]); +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; i++; - for (int ti = i; ti > 0; ti -= ti & -ti) + ll res = 0; + for (int ti = i; ti > 0; ti &= ti-1) res += add[ti] * i + mul[ti]; return res; } diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp index ab91364..a5be822 100644 --- a/content/datastructures/lazyPropagation.cpp +++ b/content/datastructures/lazyPropagation.cpp @@ -1,23 +1,22 @@ struct SegTree { using T = ll; using U = ll; - int n; static constexpr T E = 0; // Neutral element for combine - static constexpr U UF = INF; // Unused value by updates - vector<T> tree; + static constexpr U UF = 1e18; // Unused value by updates + int n; + vector<T> tree; vector<U> lazy; int h; - vector<U> lazy; - vector<int> k; // size of segments (optional) + vector<ll> k; // size of segments (optional) - SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E), + SegTree(const vector<T>& a) : n(ssize(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); + 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 + 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]; @@ -44,17 +43,17 @@ struct SegTree { void update(int l, int r, U val) { l += n, r += n; int l0 = l, r0 = r; - push(l0), push(r0 - 1); + 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 - 1); + build(l0), build(r0); } T query(int l, int r) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); T resL = E, resR = E; for (; l < r; l /= 2, r /= 2) { if (l&1) resL = comb(resL, tree[l++]); @@ -64,21 +63,23 @@ struct SegTree { } // Optional: - int lower_bound(int l, int r, T x) { + int binary_search(int l, int r, auto &&f) { + if (f(E)) return l; l += n, r += n; - push(l), push(r - 1); + push(l), push(r); 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 + T x = E, y = x; + for (int i : a) if (i != 0 && f(x = comb(y = x, tree[i]))) { while (i < n) { push_down(i); - if (tree[2 * i] >= x) i = 2 * i; // And this - else i = 2 * i + 1; + if (f(x = comb(y, tree[2*i]))) i = 2 * i; + else i = 2 * i + 1, y = x; } - return i - n; + return i - n + 1; } return -1; } diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index 1318ca7..bdbf5f9 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -1,9 +1,10 @@ vector<ll> xs; // IMPORTANT: Initialize before constructing! -int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} +int findX(int i) { + return ranges::lower_bound(xs, i) - begin(xs); } -struct Fun { // Default: Linear function. Change as needed. +struct Fun { // Default: Linear function. Change as needed. ll m, c; - ll operator()(int x) {return m*xs[x] + c;} + ll operator()(int x) { return m*xs[x] + c; } }; // Default: Computes min. Change lines with comment for max. @@ -11,18 +12,18 @@ 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) {} - + Lichao() : n(ssize(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;} + 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 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); @@ -42,5 +43,5 @@ struct Lichao { } return ans; } - ll query(ll x) {return _query(findX(x));} + ll query(ll x) { return _query(findX(x)); } }; diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index f1721ae..295acc4 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,25 @@ -// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue -// Gerade hat kleineres pair(m, c) als alle vorherigen. -struct Line { - ll m, c; - ll operator()(ll x) {return m*x+c;} -}; +struct Envelope { + struct Line { + ll m, b; + ll operator()(ll x) { return m*x+b; } + }; -vector<Line> ls; -ll ptr = 0; + vector<Line> ls; + int ptr = 0; -bool bad(Line l1, Line l2, Line l3) { - return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); -} + 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 c) { // m fallend, Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { - ls.pop_back(); + void add(ll m, ll b) { + while (ssize(ls) > 1 + && bad(ls.end()[-2], ls.back(), {m,b})) ls.pop_back(); + ls.push_back({m, b}); + ptr = min(ptr, (int)ssize(ls) - 1); } - ls.push_back({m, c}); - ptr = min(ptr, sz(ls) - 1); -} -ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert - ptr = min(ptr, sz(ls) - 1); - while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; - return ls[ptr](x); -}
\ No newline at end of file + ll query(ll x) { + while (ptr < ssize(ls)-1 && ls[ptr+1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); + } +}; diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp index de0ace6..734bf91 100644 --- a/content/datastructures/pbds.cpp +++ b/content/datastructures/pbds.cpp @@ -1,14 +1,22 @@ +#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 -// *T.find_by_order(k): k-th element +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 { +template<typename T> struct chash { size_t operator()(T o) const { return __builtin_bswap64(hash<T>()(o) * RNG); }}; diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp index f26680d..ed2f891 100644 --- a/content/datastructures/persistent.cpp +++ b/content/datastructures/persistent.cpp @@ -1,18 +1,18 @@ -template<typename T>
-struct persistent {
- int& time;
- vector<pair<int, T>> data;
-
- persistent(int& time, T value = {})
- : time(time), data(1, {2*time, value}) {}
-
- T get(int t) {
- return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;
- }
-
- int set(T value) {
- time++;
- data.push_back({2*time, value});
- return time;
- }
-};
+template<typename T> +struct persistent { + int& time; + vector<pair<int, T>> data; + + persistent(int& time, T value = {}) + : time(time), data(1, {2*time, value}) {} + + T get(int t) { + return ranges::upper_bound(data,pair{2*t+1, T{}})[-1].second; + } + + int set(T value) { + time++; + data.push_back({2*time, value}); + return time; + } +}; diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp index 8326700..903bd0e 100644 --- a/content/datastructures/persistentArray.cpp +++ b/content/datastructures/persistentArray.cpp @@ -1,24 +1,24 @@ -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, data[p].set(value)});
- return mods.back().second;
- }
-
- void reset(int t) {
- while (!mods.empty() && mods.back().second > t) {
- data[mods.back().first].data.pop_back();
- mods.pop_back();
- }
- time = t;
- }
-};
+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, data[p].set(value)}); + return mods.back().second; + } + + 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/content/datastructures/segmentTree.cpp b/content/datastructures/segmentTree.cpp index 6b69d0b..1fbf886 100644 --- a/content/datastructures/segmentTree.cpp +++ b/content/datastructures/segmentTree.cpp @@ -4,14 +4,15 @@ struct SegTree { 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); + 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 + 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 diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp index b3f946e..5455ef5 100644 --- a/content/datastructures/sparseTable.cpp +++ b/content/datastructures/sparseTable.cpp @@ -6,17 +6,17 @@ struct SparseTable { return a[lidx] <= a[ridx] ? lidx : ridx; } - void init(vector<ll>* vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = ssize(vec); + a = vec.data(); st.assign(__lg(n) + 1, vector<int>(n)); - iota(all(st[0]), 0); + iota(begin(st[0]), end(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 query(int l, int r) { if (r <= l) return -1; int j = __lg(r - l); //31 - builtin_clz(r - l); return better(st[j][l] , st[j][r - (1 << j)]); diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp index 55165d4..bcf6b2e 100644 --- a/content/datastructures/sparseTableDisjoint.cpp +++ b/content/datastructures/sparseTableDisjoint.cpp @@ -7,16 +7,16 @@ struct DisjointST { return x + y; } - void init(vector<ll>* vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = ssize(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)); + 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->at(i - 1), dst[h][i]); + dst[h][i - 1] = combine(vec[i - 1], dst[h][i]); }}} ll query(int l, int r) { diff --git a/content/datastructures/stlHashMap.cpp b/content/datastructures/stlHashMap.cpp deleted file mode 100644 index b107dde..0000000 --- a/content/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/content/datastructures/stlPriorityQueue.cpp b/content/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 32b2455..0000000 --- a/content/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/content/datastructures/stlTree.cpp b/content/datastructures/stlTree.cpp deleted file mode 100644 index fbb68b9..0000000 --- a/content/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/content/datastructures/treap.cpp b/content/datastructures/treap.cpp index c5a60e9..bddfdb4 100644 --- a/content/datastructures/treap.cpp +++ b/content/datastructures/treap.cpp @@ -66,7 +66,7 @@ struct Treap { 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); + left = merge(left, ssize(treap) - 1); root = merge(left, right); } diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp index 090cdb2..55167b6 100644 --- a/content/datastructures/waveletTree.cpp +++ b/content/datastructures/waveletTree.cpp @@ -1,25 +1,20 @@ struct WaveletTree { - using it = vector<ll>::iterator; - WaveletTree *ln = nullptr, *rn = nullptr; + unique_ptr<WaveletTree> ln, rn; 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) { + 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 (it c = from; c != to; c++) { - b.push_back(b.back() + f(*c)); - } + auto f = [&](ll x) { return x < mid; }; + for (ll x: in) b.push_back(b.back() + f(x)); if (lo + 1 >= hi) return; - it pivot = stable_partition(from, to, f); - ln = new WaveletTree(from, pivot); - rn = new WaveletTree(pivot, to); + auto right = ranges::stable_partition(in, f); + ln = make_unique<WaveletTree>( + ranges::subrange(begin(in), begin(right))); + rn = make_unique<WaveletTree>(right); } - // kth element in sort[l, r) all 0-indexed ll kth(int l, int r, int k) { if (k < 0 || l + k >= r) return -1; if (lo + 1 >= hi) return lo; @@ -28,13 +23,10 @@ struct WaveletTree { 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;} }; |