【LG4148】简单题

【LG4148】简单题

题面

洛谷

题解

(kdt)模板题呀。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
inline int gi() {
	register int data = 0, w = 1;
	register char ch = 0;
	while (!isdigit(ch) && ch != '-') ch = getchar(); 
	if (ch == '-') w = -1, ch = getchar();
	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
	return w * data; 
}
void chkmin(int &x, int y) { if (x > y) x = y; } 
void chkmax(int &x, int y) { if (x < y) x = y; } 
const int MAX_N = 4e5 + 5;
const double alpha = 0.75;
const int INF = 1e9; 
struct Point { int x[2], w; } p[MAX_N]; 
struct Node {
	int mn[2], mx[2]; 
	int ls, rs, sum, size;
	Point tp; 
} t[MAX_N]; 
int ans, N, M, WD, cur, top, rt, rub[MAX_N]; 
inline bool operator < (const Point &l, const Point &r) { return l.x[WD] < r.x[WD]; } 
inline int newnode() {
	if (top) return rub[top--]; 
	else return ++cur; 
}
void pushup(int o) {
	int ls = t[o].ls, rs = t[o].rs; 
	for (int i = 0; i <= 1; i++) {
		t[o].mn[i] = t[o].mx[i] = t[o].tp.x[i]; 
		if (ls) chkmin(t[o].mn[i], t[ls].mn[i]), chkmax(t[o].mx[i], t[ls].mx[i]); 
		if (rs) chkmin(t[o].mn[i], t[rs].mn[i]), chkmax(t[o].mx[i], t[rs].mx[i]); 
	} 
	t[o].sum = t[ls].sum + t[rs].sum + t[o].tp.w, t[o].size = t[ls].size + t[rs].size + 1; 
} 
int build(int l, int r, int wd) { 
	if (l > r) return 0; 
	int mid = (l + r) >> 1, o = newnode(); 
	WD = wd, nth_element(&p[l], &p[mid], &p[r + 1]), t[o].tp = p[mid]; 
	t[o].ls = build(l, mid - 1, wd ^ 1), t[o].rs = build(mid + 1, r, wd ^ 1); 
	return pushup(o), o; 
} 
void pia(int o, int num) {
	if (t[o].ls) pia(t[o].ls, num); 
	p[num + t[t[o].ls].size + 1] = t[o].tp, rub[++top] = o; 
	if (t[o].rs) pia(t[o].rs, num + t[t[o].ls].size + 1); 
} 
void check(int &o, int wd) { 
	if (alpha * t[o].size < t[t[o].ls].size || alpha * t[o].size < t[t[o].rs].size) 
		pia(o, 0), o = build(1, t[o].size, wd); 
} 
void insert(int &o, int wd, Point tmp) { 
	if (!o) return (void)(o = newnode(), t[o].ls = t[o].rs = 0, t[o].tp = tmp, pushup(o)); 
	if (tmp.x[wd] <= t[o].tp.x[wd]) insert(t[o].ls, wd ^ 1, tmp); 
	else insert(t[o].rs, wd ^ 1, tmp);
	pushup(o), check(o, wd); 
}
bool inner(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) { return (X1 >= x1 && X2 <= x2 && Y1 >= y1 && Y2 <= y2); } 
int outter(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) { return (x1 > X2 || x2 < X1 || y1 > Y2 || y2 < Y1); } 
int query(int o, int x1, int y1, int x2, int y2) { 
	if (!o) return 0; 
	int res = 0;
	if (inner(x1, y1, x2, y2, t[o].mn[0], t[o].mn[1], t[o].mx[0], t[o].mx[1])) return t[o].sum;
    if (outter(x1, y1, x2, y2, t[o].mn[0], t[o].mn[1], t[o].mx[0], t[o].mx[1])) return 0;
    if (inner(x1, y1, x2, y2, t[o].tp.x[0], t[o].tp.x[1], t[o].tp.x[0], t[o].tp.x[1])) res += t[o].tp.w; 
    res += query(t[o].ls, x1, y1, x2, y2) + query(t[o].rs, x1, y1, x2, y2); 
    return res; 
} 
int main () {
	N = gi(); 
	for ( ; ; ) {
		int op = gi(); if (op == 3) break; 
		if (op == 1) insert(rt, 0, (Point){gi()^ ans, gi() ^ ans, gi() ^ ans});
		else {
			int x1 = gi() ^ ans, y1 = gi() ^ ans, x2 = gi() ^ ans, y2 = gi() ^ ans; 
			printf("%d
", ans = query(rt, x1, y1, x2, y2)); 
		} 
	} 
	return 0; 
}