// MagicDark #include <bits/stdc++.h> #define debug cerr << "\33[32m[" << __LINE__ << "]\33[m " #define SZ(x) ((int) x.size() - 1) #define all(x) x.begin(), x.end() #define ms(x, y) memset(x, y, sizeof x) #define F(i, x, y) for (int i = (x); i <= (y); i++) #define DF(i, x, y) for (int i = (x); i >= (y); i--) using namespace std; typedef long long ll; typedef unsigned long long ull; template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);} template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);} template <typename T> T& read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x *= f; } int n, m, k, q; struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(pair <int, int> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(((uint64_t) x.first << 32 | x.second) + FIXED_RANDOM); } }; unordered_set <pair <int, int>, custom_hash> id; // const int dx[4] = {-1, 1, 0, 0}; // const int dy[4] = {0, 0, -1, 1}; int ans, cur; void work() { int x, y; read(x), read(y); F(a, x - 1, x + 1) F(b, y - 1, y + 1) { if (id.count(make_pair(a, b))) { bool flag = false; for (int c: {-1, 1}) { for (int d: {-1, 1}) { if (id.count(make_pair(a + c, b)) && id.count(make_pair(a, b + d)) && id.count(make_pair(a + c, b + d))) { flag = true; break; } } if (flag) break; } ans -= flag; } } if (id.count(make_pair(x, y))) id.erase(make_pair(x, y)), cur--; else id.insert(make_pair(x, y)), cur++; F(a, x - 1, x + 1) F(b, y - 1, y + 1) { if (id.count(make_pair(a, b))) { bool flag = false; for (int c: {-1, 1}) { for (int d: {-1, 1}) { if (id.count(make_pair(a + c, b)) && id.count(make_pair(a, b + d)) && id.count(make_pair(a + c, b + d))) { flag = true; break; } } if (flag) break; } ans += flag; } } } signed main() { read(n), read(m), read(k), read(q); F(i, 1, k) { work(); } cout << cur - ans << '\n'; while (q--) { work(); cout << cur - ans << '\n'; } return 0; } /* why? */
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 | // MagicDark #include <bits/stdc++.h> #define debug cerr << "\33[32m[" << __LINE__ << "]\33[m " #define SZ(x) ((int) x.size() - 1) #define all(x) x.begin(), x.end() #define ms(x, y) memset(x, y, sizeof x) #define F(i, x, y) for (int i = (x); i <= (y); i++) #define DF(i, x, y) for (int i = (x); i >= (y); i--) using namespace std; typedef long long ll; typedef unsigned long long ull; template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);} template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);} template <typename T> T& read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x *= f; } int n, m, k, q; struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(pair <int, int> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(((uint64_t) x.first << 32 | x.second) + FIXED_RANDOM); } }; unordered_set <pair <int, int>, custom_hash> id; // const int dx[4] = {-1, 1, 0, 0}; // const int dy[4] = {0, 0, -1, 1}; int ans, cur; void work() { int x, y; read(x), read(y); F(a, x - 1, x + 1) F(b, y - 1, y + 1) { if (id.count(make_pair(a, b))) { bool flag = false; for (int c: {-1, 1}) { for (int d: {-1, 1}) { if (id.count(make_pair(a + c, b)) && id.count(make_pair(a, b + d)) && id.count(make_pair(a + c, b + d))) { flag = true; break; } } if (flag) break; } ans -= flag; } } if (id.count(make_pair(x, y))) id.erase(make_pair(x, y)), cur--; else id.insert(make_pair(x, y)), cur++; F(a, x - 1, x + 1) F(b, y - 1, y + 1) { if (id.count(make_pair(a, b))) { bool flag = false; for (int c: {-1, 1}) { for (int d: {-1, 1}) { if (id.count(make_pair(a + c, b)) && id.count(make_pair(a, b + d)) && id.count(make_pair(a + c, b + d))) { flag = true; break; } } if (flag) break; } ans += flag; } } } signed main() { read(n), read(m), read(k), read(q); F(i, 1, k) { work(); } cout << cur - ans << '\n'; while (q--) { work(); cout << cur - ans << '\n'; } return 0; } /* why? */ |