重点在于如何找到某一个方向上最近的墙。 一开始想复杂了:用二维树状数组维护二维前缀和,进行单点更新和区间查询,就能知道某一区域没被毁的格点数量;给定格点后,可以二分距离找到最近的没被毁的格点,用前缀和检查距离内是否有未被毁格点。 实际上用 set 维护每行每列未被毁的格点即可。需要注意的是 set 坑点很多:
#include<iostream> #include<set> #include<vector> usingnamespace std; int h, w, q; vector<set<int>> remained_row; vector<set<int>> remained_col; vector<vector<bool>> vis; intmain() { cin >> h >> w >> q; remained_row.resize(h + 1); remained_col.resize(w + 1); vis.resize(h + 1, vector<bool>(w + 1, true)); for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { remained_row[i].emplace(j); } } for (int j = 1; j <= w; j++) { for (int i = 1; i <= h; i++) { remained_col[j].emplace(i); } } while (q--) { int r, c; scanf("%d%d", &r, &c); if (vis[r][c]) { vis[r][c] = false; remained_row[r].erase(remained_row[r].find(c)); remained_col[c].erase(remained_col[c].find(r)); } else { if (!remained_row[r].empty()) { auto R = remained_row[r].upper_bound(c); if (R != remained_row[r].end()) { vis[r][*R] = false; remained_col[*R].erase(r); remained_row[r].erase(R); } if (!remained_row[r].empty()) { auto L = remained_row[r].upper_bound(c); if (L != remained_row[r].begin()) { L = prev(L); vis[r][*L] = false; remained_col[*L].erase(r); remained_row[r].erase(L); } } }
if (!remained_col[c].empty()) { auto D = remained_col[c].upper_bound(r); if (D != remained_col[c].end()) { vis[*D][c] = false; remained_row[*D].erase(c); remained_col[c].erase(D); } if (!remained_col[c].empty()) { auto U = remained_col[c].upper_bound(r); if (U != remained_col[c].begin()) { U = prev(U); vis[*U][c] = false; remained_row[*U].erase(c); remained_col[c].erase(U); } } } } } int ans = 0; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { if (vis[i][j]) { ans++; } } } cout << ans << endl; return0; }