#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second pair<int, int> pom[4]; set<pair<int, int>> S; map<pair<int, int>, int> na_co; const int MAXP = 2e5 + 7; int kier[MAXP][4]; bool czy[MAXP]; bool odw[MAXP]; int liczba; void licz() { queue<int> q; rep(i, liczba) { if (czy[i]) { if ((!czy[kier[i][0]]) && (!czy[kier[i][1]])) { q.push(i); } else if ((!czy[kier[i][2]]) && (!czy[kier[i][3]])) { q.push(i); } } } int ans = 0; while (!q.empty()) { int v = q.front(); q.pop(); if (odw[v]) { continue; } odw[v] = true; ans++; rep(c, 4) { int w = kier[v][c]; if (!czy[w]) { continue; } if (odw[w]) { continue; } int a1 = kier[w][0]; int b1 = kier[w][1]; int a2 = kier[w][2]; int b2 = kier[w][3]; if (((!czy[a1]) || odw[a1]) && ((!czy[b1]) || odw[b1])) { q.push(w); } else if (((!czy[a2]) || odw[a2]) && ((!czy[b2]) || odw[b2])) { q.push(w); } } } cout << ans << '\n'; rep(i, liczba) { odw[i] = false; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); pom[0] = {-1, 0}; pom[1] = {1, 0}; pom[2] = {0, -1}; pom[3] = {0, 1}; int n, m, k, q; cin >> n >> m >> k >> q; pair<int, int> T[k]; int kt = 1; rep(i, k) { cin >> T[i].st >> T[i].nd; if (S.find(T[i]) == S.end()) { S.insert(T[i]); na_co[T[i]] = kt; kt++; } } pair<int, int> zmiany[q]; rep(i, q) { cin >> zmiany[i].st >> zmiany[i].nd; if (S.find(zmiany[i]) == S.end()) { S.insert(zmiany[i]); na_co[zmiany[i]] = kt; kt++; } } for (auto p: S) { int v = na_co[p]; rep(i, 4) { int x = p.st + pom[i].st; int y = p.nd + pom[i].nd; if (S.find({x, y}) == S.end()) { kier[v][i] = 0; } else { kier[v][i] = na_co[{x, y}]; } } } rep(i, k) { int v = na_co[T[i]]; czy[v] = true; liczba = max(liczba, v + 1); } licz(); rep(i, q) { int v = na_co[zmiany[i]]; liczba = max(liczba, v + 1); if (czy[v]) { czy[v] = false; } else { czy[v] = true; } licz(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second pair<int, int> pom[4]; set<pair<int, int>> S; map<pair<int, int>, int> na_co; const int MAXP = 2e5 + 7; int kier[MAXP][4]; bool czy[MAXP]; bool odw[MAXP]; int liczba; void licz() { queue<int> q; rep(i, liczba) { if (czy[i]) { if ((!czy[kier[i][0]]) && (!czy[kier[i][1]])) { q.push(i); } else if ((!czy[kier[i][2]]) && (!czy[kier[i][3]])) { q.push(i); } } } int ans = 0; while (!q.empty()) { int v = q.front(); q.pop(); if (odw[v]) { continue; } odw[v] = true; ans++; rep(c, 4) { int w = kier[v][c]; if (!czy[w]) { continue; } if (odw[w]) { continue; } int a1 = kier[w][0]; int b1 = kier[w][1]; int a2 = kier[w][2]; int b2 = kier[w][3]; if (((!czy[a1]) || odw[a1]) && ((!czy[b1]) || odw[b1])) { q.push(w); } else if (((!czy[a2]) || odw[a2]) && ((!czy[b2]) || odw[b2])) { q.push(w); } } } cout << ans << '\n'; rep(i, liczba) { odw[i] = false; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); pom[0] = {-1, 0}; pom[1] = {1, 0}; pom[2] = {0, -1}; pom[3] = {0, 1}; int n, m, k, q; cin >> n >> m >> k >> q; pair<int, int> T[k]; int kt = 1; rep(i, k) { cin >> T[i].st >> T[i].nd; if (S.find(T[i]) == S.end()) { S.insert(T[i]); na_co[T[i]] = kt; kt++; } } pair<int, int> zmiany[q]; rep(i, q) { cin >> zmiany[i].st >> zmiany[i].nd; if (S.find(zmiany[i]) == S.end()) { S.insert(zmiany[i]); na_co[zmiany[i]] = kt; kt++; } } for (auto p: S) { int v = na_co[p]; rep(i, 4) { int x = p.st + pom[i].st; int y = p.nd + pom[i].nd; if (S.find({x, y}) == S.end()) { kier[v][i] = 0; } else { kier[v][i] = na_co[{x, y}]; } } } rep(i, k) { int v = na_co[T[i]]; czy[v] = true; liczba = max(liczba, v + 1); } licz(); rep(i, q) { int v = na_co[zmiany[i]]; liczba = max(liczba, v + 1); if (czy[v]) { czy[v] = false; } else { czy[v] = true; } licz(); } return 0; } |