diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/lazyPropagation.cpp | 11 | ||||
| -rw-r--r-- | datastructures/unionFind.cpp | 10 |
2 files changed, 12 insertions, 9 deletions
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 3d3ea6b..2202a6f 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -65,14 +65,13 @@ struct SegTree { // Optional: ll lower_bound(int l, int r, T x) { l += n, r += n; - push(l), push(r); - vector<int> a, st; + push(l), push(r - 1); + 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/unionFind.cpp b/datastructures/unionFind.cpp index 35843cd..68eef86 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,5 +1,5 @@ // unions[i] >= 0 => unions[i] = parent -// unions[i] < 0 => unions[i] = -height +// unions[i] < 0 => unions[i] = -size vector<int> unions; void init(int n) { //Initialisieren @@ -11,12 +11,16 @@ int findSet(int n) { // Pfadkompression return unions[n] = findSet(unions[n]); } -void linkSets(int a, int b) { // Union by rank. +void linkSets(int a, int b) { // Union by size. if (unions[b] > unions[a]) swap(a, b); - if (unions[b] == unions[a]) unions[b]--; + unions[b] += unions[a]; unions[a] = b; } void unionSets(int a, int b) { // Diese Funktion aufrufen. if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); } + +int size(int a) { + return -unions[findSet(a)]; +} |