题意：

输入一个M，然后M次操作。'B'表示增加一个点，坐标为(x, y)，如果存在不操作。'D'表示删除一个点，坐标为(x, y)，如果不存在不操作。'Q'表示一次询问，输出给定范围内点的个数。

思路1：

如果本题将二维转换成一维。可以用前缀和的思想，假如求线段[y1, y2]上面点的数量可以用[0, y2]上面点的数量减去[0, y1 - 1]上面点的数量，这是基础的树状数组。那么由于输入的坐标都是整数，且x和y的范围都在1000以内，我们可以开1000个树状数组进行遍历。将二维转换成1000个一维；

• 解法一(数据水才过的，并不符合本题的要求)

  Accepted

  2642

  312MS

  6308K

  1775 B

  G++

  #include "bits/stdc++.h"
  using namespace std;
  const int MAXN = 1005;
  // 开MAXN个树状数组, tree[i]对应x轴为i的情况 
  int tree[MAXN][MAXN];
  // 记录各个点是否存在 
  bool bright[MAXN][MAXN];
  int lowbit(int n) {
      return n & (-n);
  }
  void add(int x, int y, int v) {
      while (y < MAXN) {
          tree[x][y] += v;
          y += lowbit(y);
      }
  }
  int query(int id, int n) {
      int res = 0;
      while (n != 0) {
          res += tree[id][n];
          n -= lowbit(n);
      }
      return res;
  }
  int main() {
      int n, x1, y1, x2, y2;
      char op;
      scanf("%d%*c", &n);
      while (n--) {
          scanf("%c", &op);
          if (op == 'Q') {
              int sum = 0;
              scanf("%d%d%d%d%*c", &x1, &x2, &y1, &y2);
              // 树状数组的0号坐标无意义，为避免使用0号坐标把所有坐标都加1，下面的x1++, y1++;也是出于同样原因 
              x1++, x2++, y1++, y2++;
              // 题中没有说明x1, x2的大小和y1, y2的大小，所以要判断一下。在此栽过 
              if (x1 > x2) {
                  swap(x1, x2);
              }
              if (y1 > y2) {
                  swap(y1, y2);
              }
              for (int i = x1; i <= x2; i++) {
                  sum += query(i, y2) - query(i, y1 - 1);
              }
              printf("%d\n", sum);
          } else {
              scanf("%d%d%*c", &x1, &y1);
              x1++, y1++;
              if (op == 'B') {
                  if (bright[x1][y1]) {
                      continue;
                  }
                  add(x1, y1, 1);
                  bright[x1][y1] = true;
              } else {
                  if (!bright[x1][y1]) {
                      continue;
                  }
                  add(x1, y1, -1);
                  bright[x1][y1] = false;
              }
          }
      }
      return 0;
  } 

  看上去不错，能AC，312MS。别开玩笑了，这完全是因为数据水。让我们算一下复杂度：对于每次查询，遍历x1到x2，最多1000次，树状数组查询是log的，再乘log1000(大约是10)，操作次数的上限是100000。乘一下就是1e9。这个运算量不是2秒能跑出来的。