text: Examples Input 7 3 0011100 3 1 4 6 3 3 4 7 2 2 3 Output 1 2 3 3 3 3 3 Input 8 6 00110011 3 1 3 8 5 1 2 5 6 7 2 6 8 2 3 5 2 4 7 1 2 Output 1 1 1 1 1 1 4 4 Input 5 3 00011 3 1 2 3 1 4 3 3 4 5 Output 1 1 1 1 1 Input 19 5 1001001001100000110 2 2 3 2 5 6 2 8 9 5 12 13 14 15 16 1 19 Output 0 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 5 Note In the first example: * For i = 1, we can just apply one operation on A_1, the final states will be 1010110; * For i = 2, we can apply operations on A_1 and A_3, the final states will be 1100110; * For i ≥ 3, we can apply operations on A_1, A_2 and A_3, the final states will be 1111111.In the second example: * For i ≤ 6, we can just apply one operation on A_2, the final states will be 11111101; * For i ≥ 7, we can apply operations on A_1, A_3, A_4, A_6, the final states will be 11111111.# Solution #include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; int n, k; char s[maxn]; int pre[maxn << 1], sz[maxn << 1]; vector<int> op[maxn]; int find(int x) { return x == pre[x] ?x : pre[x] = find(pre[x]); } void merge(int x, int y) { int fx = find(x), fy = find(y); if (fy == 0) swap(fx, fy); if (fx != fy) pre[fy] = fx, sz[fx] += sz[fy]; } int cal(int x) { int y = (x <= k) ?x + k : x - k; int fx = find(x), fy = find(y); if (fx == 0 || fy == 0) return sz[fx + fy]; return min(sz[fx], sz[fy]); } int main() { scanf("%d%d", &n, &k); scanf("%s", s + 1); for (int i = 1; i <= k; i++) pre[i] = i, pre[i + k] = i + k, sz[i + k] = 1; for (int i = 1, c, x; i <= k; i++) { scanf("%d", &c); while (c--) { scanf("%d", &x); op[x].push_back(i); } } int res = 0; for (int i = 1; i <= n; i++) { if (op[i].size() == 1) { int x = op[i][0]; res -= cal(x); if (s[i] == '1') pre[find(x + k)] = 0; else pre[find(x)] = 0; res += cal(x); } else if (op[i].size() == 2) { int x = op[i][0], y = op[i][1]; if (s[i] == '1') { if (find(x) !