题意

有一个大小为 $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";
    }
  }
}