题意
有一个大小为 $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$ 个棋子,把最后一行的每一列都攻击掉…
由此可见,若想让一个子矩阵范围内所有位置都可以被攻击,即完整攻击,当且仅当子矩阵的每一行或每一列都能被攻击。
于是可以使用两个树状数组维护。一个维护每一行是否被攻击,一个维护每一列是否被攻击。
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";
}
}
}