CF575I Robots protection 题解

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;
}