[DAAP/H3] Reworked entirely solution with unionfind

100/100

1 files changed, 63 insertions, 48 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp
index 1d26d1d..32702f6 100644
--- a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp
+++ b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp
@@ -1,75 +1,90 @@
 #include <iostream>
+#include <cstring>
+#include <stack>
 using namespace std;
 
 typedef pair<long long, long long> Query;
 
 char S[2000005] = { '\0' };
+char Supdate[2000005] = { '\0' };
 long long QN = 0;
 Query qs[2000005] = {{0,0}};
-long long mem[2000005] = { 0 };
+long long leader[2000005] = { 0 }, ssize[2000005] = { 0 }, mem[2000005] = { 0 };
 
-char* lastLeftMatching(char* c) {
-	char* l = c;
-	while (l != S && *(l-1) == *c) {
-		l--;
+long long getLeader(long long l) {
+	while (leader[l] != l) {
+		leader[l] = leader[leader[l]];
+		l = leader[l];
 	}
 	return l;
 }
 
-char* lastRightMatching(char* c) {
-	char* r = c;
-	while (*(r+1) == *c) {
-		r++;
-	}
-	return r;
-}
-
 int main() {
-	ios::sync_with_stdio(false);
-	cin.tie(NULL);
-	cout.tie(NULL);
-
-	cin.getline(S, 2000005);
-	cin >> QN;
+	scanf("%s", S);
+	scanf("%lld", &QN);
 	for (long long i = 0; i < QN; i++) {
 		Query qi = {0,0};
-		cin >> qi.first >> qi.second;
+		scanf("%lld %lld", &qi.first, &qi.second);
 		qs[i] = qi;
 	}
+	strcpy(Supdate, S);
 
-	for (Query& q : qs) {
-		if (q.first == 2) {
-			char* l = lastLeftMatching(S + q.second), *r = lastRightMatching(S + q.second);
-			// cout << "Del " << r-l+1 << endl;
-			long long nl = (S + q.second) - l;
-			while (l <= S + q.second) {
-				mem[l-S] = nl;
-				l++;
-			}
-			nl = r - (S + q.second);
-			while (l <= r) {
-				mem[l-S] = nl;
-				l++;
-			}
-			S[q.second] = '#';
+	// Fill Supdate
+	for (long long i = 0; i < QN; i++) {
+		if (qs[i].first == 1) continue;
+		Supdate[qs[i].second] = '#';
+	}
+	// cout << endl;
+	// for (int i = 0; i <QN; i++) {
+	// 	cout << qs[i].first << " " << qs[i].second << endl;
+	// }
+
+	// Fill leader and ssize
+	for (long long i = 0; Supdate[i] != '\0'; i++) {
+		if (Supdate[i] == '#') {
+			ssize[i] = 1;
+			leader[i] = i;
+			continue;
 		}
-		else if (q.first == 1) {
-			if (mem[q.second] > 0) {
-				// cout << "From memory ";
-				cout << mem[q.second] << endl;
-				continue;
+		long long j = i;
+		while (Supdate[i] == Supdate[j]) j++;
+		long long ib = i;
+		for (; i < j; i++) {
+			ssize[i] = j - ib;
+			leader[i] = ib;
+		}
+		i--;
+	}
+	// Fix leader and size
+	long long mi = 0;
+	for (long long i = QN - 1; i >= 0; i--) {
+		if (qs[i].first == 2) {
+			Supdate[qs[i].second] = S[qs[i].second];
+			if (qs[i].second > 0 && Supdate[qs[i].second - 1] == Supdate[qs[i].second]) {
+				long long l = getLeader(qs[i].second - 1);
+				leader[l] = qs[i].second;
+				ssize[qs[i].second] += ssize[l];
 			}
-			// cout << S << endl;
-			char* l = lastLeftMatching(S + q.second), *r = lastRightMatching(S + q.second);
-			long long len = r-l+1;
-			cout << len << endl;
-			while (l <= r) {
-				mem[q.second] = len;
-				l++;
+			if (Supdate[qs[i].second] == Supdate[qs[i].second+1]) {
+				long long l = getLeader(qs[i].second + 1);
+				leader[l] = qs[i].second;
+				ssize[qs[i].second] += ssize[l];
 			}
 		}
 		else {
-			break;
+			mem[mi++] = ssize[getLeader(qs[i].second)];
+			// cout << Supdate << endl;
+			// for (int i = 0; i < 15; i++)
+			// 	cout << leader[i] << " ";
+			// cout << endl;
+			// for (int i = 0; i < 15; i++)
+			// 	cout << ssize[i] << " ";
+			// cout << endl;
+			// cout << qs[i].second << " " << leader[qs[i].second] << " " << ssize[qs[i].second] << endl;
 		}
 	}
+
+	// Output
+	while(--mi >= 0)
+		printf("%lld\n", mem[mi]);
 }