summaryrefslogtreecommitdiff
path: root/content/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'content/datastructures')
-rw-r--r--content/datastructures/datastructures.tex2
-rw-r--r--content/datastructures/dynamicConvexHull.cpp18
-rw-r--r--content/datastructures/lichao.cpp10
-rw-r--r--content/datastructures/monotonicConvexHull.cpp2
-rw-r--r--content/datastructures/pbds.cpp4
-rw-r--r--content/datastructures/persistent.cpp8
-rw-r--r--content/datastructures/persistentArray.cpp4
-rw-r--r--content/datastructures/treap.cpp140
-rw-r--r--content/datastructures/treap2.cpp79
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
-};
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:12:09 +0000