好文收藏夹

题意 你需要在平面直角坐标系上进行 $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$ 很小，二维树状数组即可。 注意到要分五类考虑，所以要在时间和空间卡一下常数。 （图来自兔） 代码 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;...