Codechef 14.9 QRECT CDQ分治+分治+线段树

#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}
int getint() {
	static int c, x;
	while (!isdigit(c = getc()));
	x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}
char getch() {
	static char c;
	while ((c = getc()) != 'I' && c != 'D' && c != 'Q');
	return c;
}

#define N 100010
struct SegmentTree {
	int a[524288], t[524288], M, tclock;
	int get(int x) {
		if (t[x] != tclock) {
			t[x] = tclock;
			a[x] = 0;
		}
		return a[x];
	}
	void add(int x, int c) {
		if (t[x] != tclock) {
			t[x] = tclock;
			a[x] = 0;
		}
		a[x] += c;
	}
	void init(int n) {
		for (M = 1; M < n + 2; M <<= 1);
		++tclock;
	}
	int query(int tl, int tr) {
		static int ans;
		ans = 0;
		for (tl += M - 1, tr += M + 1; tl ^ tr ^ 1; tl >>= 1, tr >>= 1) {
			if (~tl & 1)
				ans += get(tl ^ 1);
			if (tr & 1)
				ans += get(tr ^ 1);
		}
		return ans;
	}
	void modify(int x, int c) {
		for (x += M; x; x >>= 1)
			add(x, c);
	}
}Seg;
int dx[200010], dy[200010], idx, idy;
int findx(int x) {
	return lower_bound(dx + 1, dx + idx + 1, x) - dx;
}
int findy(int y) {
	return lower_bound(dy + 1, dy + idy + 1, y) - dy;
}

struct Rect {
	int x1, x2, y1, y2;
	void read() {
		x1 = getint();
		y1 = getint();
		x2 = getint();
		y2 = getint();
	}
};
struct Note {
	Rect x;
	int w;
}S[100010];
int ans[100010], addid[100010];
#define mp make_pair
#define fi first
#define se second
pair<int, int> diary[100010];
void solve_1d(int l, int r, bool small, bool x) {
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	solve_1d(l, mid, small, x);
	solve_1d(mid + 1, r, small, x);
	Seg.init(x ? idx : idy);
	for (int i = l; i <= mid; ++i)
		if (diary[i].se <= 0)
			Seg.modify(diary[i].fi, diary[i].se == 0 ? 1 : -1);
	for (int i = mid + 1; i <= r; ++i)
		if (diary[i].se > 0) {
			if (small)
				ans[diary[i].se] -= Seg.query(1, diary[i].fi);
			else
				ans[diary[i].se] -= Seg.query(diary[i].fi, x ? idx : idy);
		}
}
typedef pair<pair<int, int>, int> piii;
piii diary2[100010], temp[100010];
bool cmp_left(const piii &a, const piii &b) {
	if (a.fi.fi != b.fi.fi)
		return a.fi.fi < b.fi.fi;
	return a.se < b.se;
}
bool cmp_right(const piii &a, const piii &b) {
	if (a.fi.fi != b.fi.fi)
		return a.fi.fi > b.fi.fi;
	return a.se < b.se;
}
void solve_2d(int l, int r, bool left, bool down) {
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	solve_2d(l, mid, left, down);
	solve_2d(mid + 1, r, left, down);
	Seg.init(idy);
	int num = 0;
	for (int i = l; i <= mid; ++i)
		if (diary2[i].se <= 0)
			temp[++num] = diary2[i];
	for (int i = mid + 1; i <= r; ++i)
		if (diary2[i].se > 0)
			temp[++num] = diary2[i];
	if (left)
		sort(temp + 1, temp + num + 1, cmp_left);
	else
		sort(temp + 1, temp + num + 1, cmp_right);
	for (int i = 1; i <= num; ++i) {
		if (temp[i].se <= 0)
			Seg.modify(temp[i].fi.se, temp[i].se == 0 ? 1 : -1);
		else {
			if (down)
				ans[temp[i].se] += Seg.query(1, temp[i].fi.se);
			else
				ans[temp[i].se] += Seg.query(temp[i].fi.se, idy);
		}
	}
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("tt.in", "r", stdin);
	freopen("tt.out", "w", stdout);
#endif
	int q = getint();
	int i, j, tot = 0, ask = 0, add = 0;
	char ch;
	for (i = 1 ; i <= q; ++i) {
		ch = getch();
		if (ch == 'I') {
			S[i].w = 0;
			S[i].x.read();
			dx[++idx] = S[i].x.x1;
			dx[++idx] = S[i].x.x2;
			dy[++idy] = S[i].x.y1;
			dy[++idy] = S[i].x.y2;
			++tot;
			addid[++add] = i;
		}
		else if (ch == 'Q') {
			S[i].x.read();
			dx[++idx] = S[i].x.x1 - 1;
			dx[++idx] = S[i].x.x2 + 1;
			dy[++idy] = S[i].x.y1 - 1;
			dy[++idy] = S[i].x.y2 + 1;
			ans[++ask] = tot;
			S[i].w = ask;
		}
		else {
			S[i].w = -1;
			S[i].x = S[addid[getint()]].x;
			--tot;
		}
	}
	sort(dx + 1, dx + idx + 1);
	idx = unique(dx + 1, dx + idx + 1) - dx - 1;
	sort(dy + 1, dy + idy + 1);
	idy = unique(dy + 1, dy + idy + 1) - dy - 1;
	
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary[i] = mp(findx(S[i].x.x1 - 1), S[i].w);
		else
			diary[i] = mp(findx(S[i].x.x2), S[i].w);
	}
	solve_1d(1, q, 1, 1);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary[i] = mp(findy(S[i].x.y1 - 1), S[i].w);
		else
			diary[i] = mp(findy(S[i].x.y2), S[i].w);
	}
	solve_1d(1, q, 1, 0);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary[i] = mp(findx(S[i].x.x2 + 1), S[i].w);
		else
			diary[i] = mp(findx(S[i].x.x1), S[i].w);
	}
	solve_1d(1, q, 0, 1);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary[i] = mp(findy(S[i].x.y2 + 1), S[i].w);
		else
			diary[i] = mp(findy(S[i].x.y1), S[i].w);
	}
	solve_1d(1, q, 0, 0);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary2[i] = mp(mp(findx(S[i].x.x1 - 1), findy(S[i].x.y2 + 1)), S[i].w);
		else
			diary2[i] = mp(mp(findx(S[i].x.x2), findy(S[i].x.y1)), S[i].w);
	}
	solve_2d(1, q, 1, 0);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary2[i] = mp(mp(findx(S[i].x.x2 + 1), findy(S[i].x.y2 + 1)), S[i].w);
		else
			diary2[i] = mp(mp(findx(S[i].x.x1), findy(S[i].x.y1)), S[i].w);
	}
	solve_2d(1, q, 0, 0);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary2[i] = mp(mp(findx(S[i].x.x1 - 1), findy(S[i].x.y1 - 1)), S[i].w);
		else
			diary2[i] = mp(mp(findx(S[i].x.x2), findy(S[i].x.y2)), S[i].w);
	}
	solve_2d(1, q, 1, 1);
	for (i = 1; i <= q; ++i) {
		if (S[i].w > 0)
			diary2[i] = mp(mp(findx(S[i].x.x2 + 1), findy(S[i].x.y1 - 1)), S[i].w);
		else
			diary2[i] = mp(mp(findx(S[i].x.x1), findy(S[i].x.y2)), S[i].w);
	}
	solve_2d(1, q, 0, 1);
	
	for (i = 1; i <= ask; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}