题解 CF575I 【Robots protection】

> [CF575I Robots protection](https://codeforces.com/contest/575/problem/I) ## 题意 - 你需要在平面直角坐标系上进行 $q$ 次操作。 - 每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。 - 每个等腰直角三角形可以用四个参数 $dir,x,y,len$ 确定，其中 $dir \in [1,4]$ 表示三角形的方向，$(x,y)$ 表示直角的顶点坐标，$len$ 表示直角边的长度。 - 保证所有点的坐标都是整数且 $\in [1,n]$。 - $n \le 5 \times 10^3$，$q \le 10^5$。 ## 题解 $n$ 很小，二维树状数组即可。 注意到要分五类考虑，所以要在时间和空间卡一下常数。  （图来自兔） ## 代码 ```cpp const int N = 1e4 + 7, M = 1e5 + 7; int n, m, op[M], dir[M], x[M], y[M], c[M], ans[M]; int X, Y, bit[N][N], stx[M], sty[M], stz[M], top; inline void add(int x, int y, int z) { stx[++top] = x, sty[top] = y, stz[top] = z; for (int i = x; i <= X; i += i & -i) for (int j = y; j <= Y; j += j & -j) bit[i][j] += z; } inline int ask(int x, int y) { int z = 0; for (int i = x; i; i -= i & -i) for (int j = y; j; j -= j & -j) z += bit[i][j]; return z; } inline void clear() { while (top) add(stx[top], sty[top], -stz[top]), top -= 2; } int main() { rd(n), rd(m); for (int i = 1; i <= m; i++) { rd(op[i]); if (op[i] == 1) rd(dir[i]), rd(x[i]), rd(y[i]), rd(c[i]); else rd(x[i]), rd(y[i]); } X = n, Y = n; for (int i = 1; i <= m; i++) if (op[i] == 1) { if (dir[i] == 1) add(x[i], y[i], 1); if (dir[i] == 2) add(x[i], y[i] + 1, -1); if (dir[i] == 3) add(x[i] + 1, y[i], -1); if (dir[i] == 4) add(x[i] + 1, y[i] + 1, 1); } else ans[i] += ask(x[i], y[i]); clear(); X = n + n, Y = n; for (int i = 1; i <= m; i++) if (op[i] == 1) { if (dir[i] == 1) add(x[i] + y[i] + c[i] + 1, y[i], -1); if (dir[i] == 4) add(x[i] + y[i] - c[i], y[i] + 1, -1); } else ans[i] += ask(x[i] + y[i], y[i]); clear(); X = n, Y = n + n; for (int i = 1; i <= m; i++) if (op[i] == 1) { if (dir[i] == 1) add(n - x[i] + 2, x[i] + y[i] + c[i] + 1, 1); if (dir[i] == 4) add(n - x[i] + 1, x[i] + y[i] - c[i], 1); } else ans[i] += ask(n - x[i] + 1, x[i] + y[i]); clear(); X = n + n, Y = n; for (int i = 1; i <= m; i++) if (op[i] == 1) { if (dir[i] == 2) add(n + x[i] - y[i] + c[i] + 2, y[i] + 1, 1); if (dir[i] == 3) add(n + x[i] - y[i] - c[i] + 1, y[i], 1); } else ans[i] += ask(n + x[i] - y[i] + 1, y[i]); clear(); X = n, Y = n + n; for (int i = 1; i <= m; i++) if (op[i] == 1) { if (dir[i] == 2) add(x[i], n - x[i] + y[i] - c[i] + 1, 1); if (dir[i] == 3) add(x[i] + 1, n - x[i] + y[i] + c[i] + 2, 1); } else ans[i] += ask(x[i], n - x[i] + y[i] + 1); clear(); for (int i = 1; i <= m; i++) if (op[i] == 2) printf("%d\n", ans[i]); return 0; } ```