merge mzuenni changes

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)];
+}