WA 0 分求助
查看原帖
WA 0 分求助
448887
cancan123456楼主2023/1/14 08:43
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node {
	int x, y, t, id, op, num;
} node[200005];
bool cmp1(const Node & a, const Node & b) {
	if (a.x != b.x) {
		return a.x < b.x;
	}
	if (a.y != b.y) {
		return a.y < b.y;
	}
	return a.t < b.t;
}
bool cmp2(const Node & a, const Node & b) {
	if (a.y != b.y) {
		return a.y < b.y;
	}
	return a.t < b.t;
}
int ans[10005];
int c[200005], len;
int lowbit(int x) {
	return x & -x;
}
void add(int x, int v) {
	while (x <= len) {
		c[x] += v;
		x += lowbit(x);
	}
}
int query(int x) {
	int ans = 0;
	while (x > 0) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}
void cdq(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	cdq(l, mid);
	cdq(mid + 1, r);
	sort(node + l, node + mid + 1, cmp2);
	sort(node + mid + 1, node + r + 1, cmp2);
	int i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (node[i].y <= node[j].y) {
			if (node[i].op == 0) {
				add(node[i].t, node[i].num);
			}
			i++;
		} else {
			if (node[j].op != 0) {
				ans[node[j].id] += node[j].op * query(node[j].t);
			}
			j++;
		}
	}
	while (j <= r) {
		if (node[j].op != 0) {
			ans[node[j].id] += node[j].op * query(node[j].t);
		}
		j++;
	}
	for (int k = l; k < i; k++) {
		if (node[k].op == 0) {
			add(node[i].t, -node[i].num);
		}
	}
}
int main() {
	scanf("%*d %*d");
	int op, timer = 0, qcnt = 0;
	while (true) {
		scanf("%d", &op);
		if (op == 1) {
			int x, y, a;
			scanf("%d %d %d", &x, &y, &a);
			timer++;
			len++;
			node[len].x = x;
			node[len].y = y;
			node[len].t = timer;
			node[len].op = 0;
			node[len].num = a;
		} else if (op == 2) {
			int x1, y1, x2, y2;
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			timer++;
			len++;
			qcnt++;
			node[len].x = x2;
			node[len].y = y2;
			node[len].t = timer;
			node[len].id = qcnt;
			node[len].op = 1;
			len++;
			node[len].x = x1 - 1;
			node[len].y = y2;
			node[len].t = timer;
			node[len].id = qcnt;
			node[len].op = -1;
			len++;
			node[len].x = x2;
			node[len].y = y1 - 1;
			node[len].t = timer;
			node[len].id = qcnt;
			node[len].op = -1;
			len++;
			node[len].x = x1 - 1;
			node[len].y = y1 - 1;
			node[len].t = timer;
			node[len].id = qcnt;
			node[len].op = 1;
		} else {
			break;
		}
	}
	sort(node + 1, node + len + 1, cmp1);
	cdq(1, len);
	for (int i = 1; i <= qcnt; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

似乎有些输出了负数

2023/1/14 08:43
加载中...