#include <bits/stdc++.h> using namespace std; using ll = long long; struct PairHash { size_t operator()(const pair<int, int>& p) const { return (ll(p.first) << 32) | p.second; } }; unordered_map<int, unordered_set<int>> row_map, col_map; unordered_set<pair<int, int>, PairHash> current_blocks; unordered_map<int, int> row_degree, col_degree; unordered_map<int, bool> active_row, active_col; ll core_size = 0; queue<pair<bool, int>> processing_queue; void process_queue() { while (!processing_queue.empty()) { auto entry = processing_queue.front(); processing_queue.pop(); bool is_col = entry.first; int idx = entry.second; if (is_col) { if (!active_col[idx]) continue; active_col[idx] = false; for (int x : col_map[idx]) { if (current_blocks.count({x, idx}) && active_row[x]) { core_size--; } row_map[x].erase(idx); row_degree[x]--; if (active_row[x] && row_degree[x] < 2) { processing_queue.push({false, x}); } } col_map[idx].clear(); col_degree[idx] = 0; } else { if (!active_row[idx]) continue; active_row[idx] = false; for (int y : row_map[idx]) { if (current_blocks.count({idx, y}) && active_col[y]) { core_size--; } col_map[y].erase(idx); col_degree[y]--; if (active_col[y] && col_degree[y] < 2) { processing_queue.push({true, y}); } } row_map[idx].clear(); row_degree[idx] = 0; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, k, q; cin >> n >> m >> k >> q; current_blocks.reserve(k + q); row_map.reserve(n + 1); col_map.reserve(m + 1); for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; current_blocks.insert({x, y}); row_map[x].insert(y); col_map[y].insert(x); row_degree[x]++; col_degree[y]++; } for (auto& p : row_degree) active_row[p.first] = true; for (auto& p : col_degree) active_col[p.first] = true; core_size = current_blocks.size(); for (auto& p : row_degree) { if (p.second < 2) processing_queue.push({false, p.first}); } for (auto& p : col_degree) { if (p.second < 2) processing_queue.push({true, p.first}); } process_queue(); cout << current_blocks.size() - core_size << '\n'; for (int i = 0; i < q; ++i) { int x, y; cin >> x >> y; pair<int, int> block = {x, y}; if (current_blocks.count(block)) { current_blocks.erase(block); row_map[x].erase(y); col_map[y].erase(x); bool was_in_core = active_row[x] && active_col[y]; row_degree[x]--; col_degree[y]--; if (was_in_core) core_size--; if (active_row[x] && row_degree[x] < 2) processing_queue.push({false, x}); if (active_col[y] && col_degree[y] < 2) processing_queue.push({true, y}); } else { current_blocks.insert(block); row_map[x].insert(y); col_map[y].insert(x); bool is_in_core = active_row[x] && active_col[y]; row_degree[x]++; col_degree[y]++; if (is_in_core) core_size++; } process_queue(); cout << current_blocks.size() - core_size << '\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 | #include <bits/stdc++.h> using namespace std; using ll = long long; struct PairHash { size_t operator()(const pair<int, int>& p) const { return (ll(p.first) << 32) | p.second; } }; unordered_map<int, unordered_set<int>> row_map, col_map; unordered_set<pair<int, int>, PairHash> current_blocks; unordered_map<int, int> row_degree, col_degree; unordered_map<int, bool> active_row, active_col; ll core_size = 0; queue<pair<bool, int>> processing_queue; void process_queue() { while (!processing_queue.empty()) { auto entry = processing_queue.front(); processing_queue.pop(); bool is_col = entry.first; int idx = entry.second; if (is_col) { if (!active_col[idx]) continue; active_col[idx] = false; for (int x : col_map[idx]) { if (current_blocks.count({x, idx}) && active_row[x]) { core_size--; } row_map[x].erase(idx); row_degree[x]--; if (active_row[x] && row_degree[x] < 2) { processing_queue.push({false, x}); } } col_map[idx].clear(); col_degree[idx] = 0; } else { if (!active_row[idx]) continue; active_row[idx] = false; for (int y : row_map[idx]) { if (current_blocks.count({idx, y}) && active_col[y]) { core_size--; } col_map[y].erase(idx); col_degree[y]--; if (active_col[y] && col_degree[y] < 2) { processing_queue.push({true, y}); } } row_map[idx].clear(); row_degree[idx] = 0; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, k, q; cin >> n >> m >> k >> q; current_blocks.reserve(k + q); row_map.reserve(n + 1); col_map.reserve(m + 1); for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; current_blocks.insert({x, y}); row_map[x].insert(y); col_map[y].insert(x); row_degree[x]++; col_degree[y]++; } for (auto& p : row_degree) active_row[p.first] = true; for (auto& p : col_degree) active_col[p.first] = true; core_size = current_blocks.size(); for (auto& p : row_degree) { if (p.second < 2) processing_queue.push({false, p.first}); } for (auto& p : col_degree) { if (p.second < 2) processing_queue.push({true, p.first}); } process_queue(); cout << current_blocks.size() - core_size << '\n'; for (int i = 0; i < q; ++i) { int x, y; cin >> x >> y; pair<int, int> block = {x, y}; if (current_blocks.count(block)) { current_blocks.erase(block); row_map[x].erase(y); col_map[y].erase(x); bool was_in_core = active_row[x] && active_col[y]; row_degree[x]--; col_degree[y]--; if (was_in_core) core_size--; if (active_row[x] && row_degree[x] < 2) processing_queue.push({false, x}); if (active_col[y] && col_degree[y] < 2) processing_queue.push({true, y}); } else { current_blocks.insert(block); row_map[x].insert(y); col_map[y].insert(x); bool is_in_core = active_row[x] && active_col[y]; row_degree[x]++; col_degree[y]++; if (is_in_core) core_size++; } process_queue(); cout << current_blocks.size() - core_size << '\n'; } return 0; } |