diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/LCT.cpp | 10 | ||||
| -rw-r--r-- | datastructures/dynamicConvexHull.cpp | 2 | ||||
| -rw-r--r-- | datastructures/monotonicConvexHull.cpp | 2 | ||||
| -rw-r--r-- | datastructures/persistent.cpp | 2 | ||||
| -rw-r--r-- | datastructures/sparseTable.cpp | 38 | ||||
| -rw-r--r-- | datastructures/stlTree.cpp | 2 | ||||
| -rw-r--r-- | datastructures/treap.cpp | 4 | ||||
| -rw-r--r-- | datastructures/waveletTree.cpp | 2 |
8 files changed, 31 insertions, 31 deletions
diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp index fe92c7f..aef45f7 100644 --- a/datastructures/LCT.cpp +++ b/datastructures/LCT.cpp @@ -42,7 +42,7 @@ struct LCT { bool isRoot() { return !parent || (parent->left != this && - parent->right != this); + parent->right != this); } void push() { @@ -54,7 +54,7 @@ struct LCT { } nodeValue = joinValueDelta(nodeValue, delta); subTreeValue = joinValueDelta(subTreeValue, - _update(delta, size)); + _update(delta, size)); if (left) left->delta = joinDeltas(left->delta, delta); if (right) right->delta = joinDeltas(right->delta, delta); delta = updateDefault; @@ -69,12 +69,12 @@ struct LCT { size = 1; if (left) { subTreeValue = _query(subTreeValue, - left->getSubtreeValue()); + left->getSubtreeValue()); size += left->size; } if (right) { subTreeValue = _query(subTreeValue, - right->getSubtreeValue()); + right->getSubtreeValue()); size += right->size; }} }; @@ -112,7 +112,7 @@ struct LCT { p->push(); x->push(); if (!p->isRoot()) rotate((x == p->left) == - (p == g->left) ? p : x); + (p == g->left) ? p : x); rotate(x); } x->push(); diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index d8a1a3b..5cdb12b 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -21,7 +21,7 @@ struct HullDynamic : public multiset<Line> { auto x = prev(y); if (z == end()) return y->m == x->m && y->b <= x->b; return (x->b - y->b)*(z->m - y->m) >= - (y->b - z->b)*(y->m - x->m); + (y->b - z->b)*(y->m - x->m); } // Variant 1: niklasb (2015) diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 8035b17..7003855 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -4,7 +4,7 @@ vector<ll> ms, bs; int ptr = 0; bool bad(int l1, int l2, int l3) { return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < - (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); + (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); } void add(ll m, ll b) { // Laufzeit O(1) amortisiert diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp index befecf7..1704ff2 100644 --- a/datastructures/persistent.cpp +++ b/datastructures/persistent.cpp @@ -8,7 +8,7 @@ struct persistent { T get(int t) {
return prev(upper_bound(all(data),
- pair<int, T>(t+1, {})))->second;
+ pair<int, T>(t+1, {})))->second;
}
int set(T value) {
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp index 3d11119..40057bd 100644 --- a/datastructures/sparseTable.cpp +++ b/datastructures/sparseTable.cpp @@ -1,24 +1,24 @@ struct SparseTable { - vector<vector<int>> st; - vector<ll> *a; + vector<vector<int>> st; + vector<ll> *a; - bool better(int lidx, int ridx) { - return a->at(lidx) <= a->at(ridx); - } + bool better(int lidx, int ridx) { + return a->at(lidx) <= a->at(ridx); + } - void init(vector<ll> *vec) { - a = vec; - st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a))); - for (int i = 0; i < sz(*a); i++) st[0][i] = i; - for (int j = 0; (2 << j) <= sz(*a); j++) { - for (int i = 0; i + (2 << j) <= sz(*a); i++) { - st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]) - ? st[j][i] : st[j][i + (1 << j)]; - }}} + void init(vector<ll> *vec) { + a = vec; + st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a))); + for (int i = 0; i < sz(*a); i++) st[0][i] = i; + for (int j = 0; (2 << j) <= sz(*a); j++) { + for (int i = 0; i + (2 << j) <= sz(*a); i++) { + st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]) + ? 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)]) - ? st[j][l] : st[j][r - (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)]) + ? st[j][l] : st[j][r - (1 << j)]; + } };
\ No newline at end of file diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp index 29491c4..0fdc480 100644 --- a/datastructures/stlTree.cpp +++ b/datastructures/stlTree.cpp @@ -3,7 +3,7 @@ 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>; + tree_order_statistics_node_update>; int main() { Tree<int> X; diff --git a/datastructures/treap.cpp b/datastructures/treap.cpp index 6296392..eef56b4 100644 --- a/datastructures/treap.cpp +++ b/datastructures/treap.cpp @@ -1,7 +1,7 @@ struct node { int key, prio, left, right, size; node(int key, int prio) : key(key), prio(prio), left(-1), - right(-1), size(1) {}; + right(-1), size(1) {}; }; vector<node> treap; @@ -13,7 +13,7 @@ int getSize(int root) { void update(int root) { if (root < 0) return; treap[root].size = 1 + getSize(treap[root].left) - + getSize(treap[root].right); + + getSize(treap[root].right); } pair<int, int> split(int root, int minKeyRight) { diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp index feef2d4..8a0e10f 100644 --- a/datastructures/waveletTree.cpp +++ b/datastructures/waveletTree.cpp @@ -38,7 +38,7 @@ public: 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);
+ rn->countSmaller(l-b[l], r-b[r], k);
}
~WaveletTree(){
|