【CF575I】Robots protection

题意

• 你需要在平面直角坐标系上进行 $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; 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;
}