「BOI2007」Mokia

传送门

把查询拆成四部分然后容斥计算答案（二维前缀和）

然后 \(\text{CDQ}\) 分治算答案。

参考代码：
#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 2e5 + 5, __ = 2e6 + 5;

int W, tr[__], num;

struct node { int opt, id, x, y, v, ans; } t[_], tt[_];

inline bool cmp(const node& a, const node& b) { return a.id < b.id; }

inline void update(int x, int v)

{ for (rg int i = x; i <= W; i += i & -i) tr[i] += v; }

inline int query(int x)

{ int res = 0; for (rg int i = x; i >= 1; i -= i & -i) res += tr[i]; return res; }

inline void CDQ(int l, int r) {

	if (l == r) return ;

	int mid = (l + r) >> 1;

	CDQ(l, mid), CDQ(mid + 1, r);

	int i = l, j = mid + 1, p = l;

	while (i <= mid && j <= r) {

		if (t[i].x <= t[j].x) { if (t[i].opt == 0) update(t[i].y, t[i].v); tt[p++] = t[i++]; }

		else { if (t[j].opt == 1) t[j].ans += query(t[j].y); tt[p++] = t[j++]; }

	}

	while (i <= mid) { if (t[i].opt == 0) update(t[i].y, t[i].v); tt[p++] = t[i++]; }

	while (j <= r) { if (t[j].opt == 1) t[j].ans += query(t[j].y); tt[p++] = t[j++]; }

	for (rg int i = l; i <= mid; ++i) if (t[i].opt == 0) update(t[i].y, -t[i].v);

	for (rg int i = l; i <= r; ++i) t[i] = tt[i];

}

int main() {

	int opt; read(opt), read(W);

	while (1) {

		read(opt); if (opt == 3) break ;

		if (opt == 1) {

			int x, y, v; read(x), read(y), read(v);

			t[++num] = (node) { 0, num, x, y, v, 0 };

		} else {

			int xl, yl, xr, yr;

			read(xl), read(yl), read(xr), read(yr);

			t[++num] = (node) { 1, num, xr, yr, 0, 0 };

			t[++num] = (node) { 1, num, xl - 1, yr, 0, 0 };

			t[++num] = (node) { 1, num, xr, yl - 1, 0, 0 };

			t[++num] = (node) { 1, num, xl - 1, yl - 1, 0, 0 };

		}

	}

	CDQ(1, num), sort(t + 1, t + num + 1, cmp);

	for (rg int i = 1; i <= num; ++i)

		if (t[i].opt == 1)

			printf("%d\n", t[i].ans - t[i + 1].ans - t[i + 2].ans + t[i + 3].ans), i += 3;

	return 0;

}
巴特西

「BOI2007」Mokia

「BOI2007」Mokia

最新文章

热门文章
