题解 CF1679C【Rooks Defenders】

## 题意 有一个大小为 $n\times n$ 的棋盘，有三种操作： - 在第 $x$ 行第 $y$ 列的位置，放置一个 Rook 棋子 - 移除在第 $x$ 行第 $y$ 列的位置已有的 Rook 棋子 - 判断在 $(x1, y1)$ 到 $(x2, y2)$ 范围内所有的位置，是否全部可以被 Rook 棋子攻击？ 注：Rook 棋子的攻击范围是，同一行 / 同一列的全部格子。 $n \leq 2 \times 10^5$。 ## 分析 考虑什么时候，一个子矩阵内所有位置都被攻击？ 如图，子矩阵（绿色区域）的第一行、第二行被攻击，是因为左侧有两个 Rook 棋子。而第三行被攻击，是因为右下角还有一个棋子。  如果移除左边两颗棋子，则第一行和第二行无法被**完整攻击**（前两行的第三列仍可被右下角棋子攻击）。 如果移除右下角的棋子，则第三行无法被攻击。 设子矩阵有 $r$ 行 $c$ 列，若前 $r-1$ 行上都已有棋子，此时最后一行还未被攻击。要么把最后一行也放上棋子，要么再放至多 $c$ 个棋子，把最后一行的每一列都攻击掉… 由此可见，若想让一个子矩阵范围内所有位置都可以被攻击，即**完整攻击**，当且仅当子矩阵的**每一行或每一列**都能被攻击。 于是可以使用两个树状数组维护。一个维护每一行是否被攻击，一个维护每一列是否被攻击。 ```cpp struct Fenwick { int n; std::vector<int> v; Fenwick(int n) : n(n), v(n + 1) {} int lowbit(int x) { return x & -x; } void add(int x, int y) { for (; x <= n; x += lowbit(x)) v[x] += y; } int sum(int x) { int res = 0; for (; x; x -= lowbit(x)) res += v[x]; return res; } int rangeSum(int l, int r) { return sum(r) - sum(l - 1); } }; void solution() { int n, q; read(n, q); std::vector<int> row(n + 1, 0), col(n + 1, 0); Fenwick bitRow(n), bitCol(n); while (q--) { int opt; read(opt); if (opt == 1) { int x, y; read(x, y); // a[x][y] = true; ++row[x]; ++col[y]; if (row[x] == 1) bitRow.add(x, 1); if (col[y] == 1) bitCol.add(y, 1); } else if (opt == 2) { int x, y; read(x, y); // a[x][y] = false; --row[x]; --col[y]; if (row[x] == 0) bitRow.add(x, -1); if (col[y] == 0) bitCol.add(y, -1); } else { int x1, y1, x2, y2; read(x1, y1, x2, y2); int rowLen = x2 - x1 + 1, colLen = y2 - y1 + 1; bool ok = false; if (bitRow.rangeSum(x1, x2) == rowLen) ok = true; if (bitCol.rangeSum(y1, y2) == colLen) ok = true; std::cout << (ok ? "YES" : "NO") << "\n"; } } } ```