#include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef uint64_t ull; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; constexpr ll LINF = 1e18; constexpr int INF = 1e9; using Blocks = unordered_map<ull, int>; constexpr pii to_indices(ull idx) { return {idx >> 32, idx & 0xFFFFFFFFull}; } constexpr ull from_indices(ull x, ull y) { return (x << 32) | y; } constexpr ull offsets[2] = {from_indices(1, 0) /* U, D */, from_indices(0, 1) /* L, R */}; bool is_free(Blocks &blocks, ull block) { return (!blocks.count(block + offsets[0]) && !blocks.count(block - offsets[0])) || (!blocks.count(block + offsets[1]) && !blocks.count(block - offsets[1])); } enum { BLOCKED = 0, FREE = 1 }; const int MAX_Q = 75001; int visited_cnt[2 * MAX_Q]; int status[2 * MAX_Q]; int visit_num = 0; bool is_vertex_free(Blocks &blocks, ull vertex) { for (int i = 0; i < 2; ++i) { auto neigh1 = blocks.find(vertex + offsets[i]); auto neigh2 = blocks.find(vertex - offsets[i]); if ((neigh1 == blocks.end() || status[neigh1->second] == FREE) && (neigh2 == blocks.end() || status[neigh2->second] == FREE)) { return true; } } return false; } void add_neigh_if_free(Blocks &blocks, queue<ull> &vertices, ull neigh) { auto neigh_it = blocks.find(neigh); if (neigh_it != blocks.end() && visited_cnt[neigh_it->second] < visit_num && status[neigh_it->second] != FREE && is_vertex_free(blocks, neigh)) { visited_cnt[neigh_it->second] = visit_num; status[neigh_it->second] = FREE; vertices.push(neigh); } } int bfs(Blocks &blocks, queue<ull> &vertices) { int result = 0; while (vertices.size() > 0) { ++result; ull block = vertices.front(); vertices.pop(); add_neigh_if_free(blocks, vertices, block + offsets[0]); add_neigh_if_free(blocks, vertices, block - offsets[0]); add_neigh_if_free(blocks, vertices, block + offsets[1]); add_neigh_if_free(blocks, vertices, block - offsets[1]); } return result; } int compute_initial(Blocks &blocks) { ++visit_num; // Get sources queue<ull> vertices; for (auto block : blocks) { status[block.second] = BLOCKED; if (is_free(blocks, block.first)) { status[block.second] = FREE; visited_cnt[block.second] = visit_num; vertices.push(block.first); } } return bfs(blocks, vertices); } int add(Blocks &blocks, ull added, int old_result) { if (is_free(blocks, added)) { status[blocks[added]] = FREE; return old_result + 1; } return compute_initial(blocks); } int remove(Blocks &blocks, ull removed, int old_result) { if (status[blocks[removed]] == FREE) { blocks.erase(removed); return old_result - 1; } blocks.erase(removed); queue<ull> vertices; vertices.push(removed); return old_result + bfs(blocks, vertices) - 1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k, q; cin >> n >> m >> k >> q; Blocks blocks; int x, y; for (int i = 0; i < k; ++i) { cin >> x >> y; blocks[from_indices(x, y)] = i; } int result = compute_initial(blocks); cout << result << '\n'; for (int i = 0; i < q; ++i) { cin >> x >> y; ull new_block = from_indices(x, y); auto block_it = blocks.find(new_block); if (block_it != blocks.end()) { result = remove(blocks, new_block, result); } else { blocks[from_indices(x, y)] = k + i; result = add(blocks, new_block, result); } // if (i == 67 || i == 66 || i == 65) { // for (auto block: blocks) { // auto idx = to_indices(block.first); // cout << idx.first << " " << idx.second << '\n'; // } // } cout << result << '\n'; } 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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | #include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef uint64_t ull; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; constexpr ll LINF = 1e18; constexpr int INF = 1e9; using Blocks = unordered_map<ull, int>; constexpr pii to_indices(ull idx) { return {idx >> 32, idx & 0xFFFFFFFFull}; } constexpr ull from_indices(ull x, ull y) { return (x << 32) | y; } constexpr ull offsets[2] = {from_indices(1, 0) /* U, D */, from_indices(0, 1) /* L, R */}; bool is_free(Blocks &blocks, ull block) { return (!blocks.count(block + offsets[0]) && !blocks.count(block - offsets[0])) || (!blocks.count(block + offsets[1]) && !blocks.count(block - offsets[1])); } enum { BLOCKED = 0, FREE = 1 }; const int MAX_Q = 75001; int visited_cnt[2 * MAX_Q]; int status[2 * MAX_Q]; int visit_num = 0; bool is_vertex_free(Blocks &blocks, ull vertex) { for (int i = 0; i < 2; ++i) { auto neigh1 = blocks.find(vertex + offsets[i]); auto neigh2 = blocks.find(vertex - offsets[i]); if ((neigh1 == blocks.end() || status[neigh1->second] == FREE) && (neigh2 == blocks.end() || status[neigh2->second] == FREE)) { return true; } } return false; } void add_neigh_if_free(Blocks &blocks, queue<ull> &vertices, ull neigh) { auto neigh_it = blocks.find(neigh); if (neigh_it != blocks.end() && visited_cnt[neigh_it->second] < visit_num && status[neigh_it->second] != FREE && is_vertex_free(blocks, neigh)) { visited_cnt[neigh_it->second] = visit_num; status[neigh_it->second] = FREE; vertices.push(neigh); } } int bfs(Blocks &blocks, queue<ull> &vertices) { int result = 0; while (vertices.size() > 0) { ++result; ull block = vertices.front(); vertices.pop(); add_neigh_if_free(blocks, vertices, block + offsets[0]); add_neigh_if_free(blocks, vertices, block - offsets[0]); add_neigh_if_free(blocks, vertices, block + offsets[1]); add_neigh_if_free(blocks, vertices, block - offsets[1]); } return result; } int compute_initial(Blocks &blocks) { ++visit_num; // Get sources queue<ull> vertices; for (auto block : blocks) { status[block.second] = BLOCKED; if (is_free(blocks, block.first)) { status[block.second] = FREE; visited_cnt[block.second] = visit_num; vertices.push(block.first); } } return bfs(blocks, vertices); } int add(Blocks &blocks, ull added, int old_result) { if (is_free(blocks, added)) { status[blocks[added]] = FREE; return old_result + 1; } return compute_initial(blocks); } int remove(Blocks &blocks, ull removed, int old_result) { if (status[blocks[removed]] == FREE) { blocks.erase(removed); return old_result - 1; } blocks.erase(removed); queue<ull> vertices; vertices.push(removed); return old_result + bfs(blocks, vertices) - 1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k, q; cin >> n >> m >> k >> q; Blocks blocks; int x, y; for (int i = 0; i < k; ++i) { cin >> x >> y; blocks[from_indices(x, y)] = i; } int result = compute_initial(blocks); cout << result << '\n'; for (int i = 0; i < q; ++i) { cin >> x >> y; ull new_block = from_indices(x, y); auto block_it = blocks.find(new_block); if (block_it != blocks.end()) { result = remove(blocks, new_block, result); } else { blocks[from_indices(x, y)] = k + i; result = add(blocks, new_block, result); } // if (i == 67 || i == 66 || i == 65) { // for (auto block: blocks) { // auto idx = to_indices(block.first); // cout << idx.first << " " << idx.second << '\n'; // } // } cout << result << '\n'; } return 0; } |