Luogu P4148 简单题（K-D Tree)

题面

题解

因为强制在线，所以我们不能$cdq$分治，所以考虑用$KDT$，$KDT$维护一个矩阵，然后询问的时候如果当前矩形在询问区间内，直接记贡献，否则判断当前点是否在矩阵内，然后左右分别递归下去判断就行了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::nth_element;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 200005;

int n, x1, x2, y1, y2, k, ans, rt, WD, top, cnt, rub[N];

struct poi { int x[2], w; } p[N];

struct node { int mi[2], mx[2], sum, lc, rc, siz; poi tp; } t[N];

int operator < (const poi &a, const poi &b) { return a.x[WD] < b.x[WD]; }

inline int newnode() { if(top) return rub[top--]; else return ++cnt; }

void up(int k) {

	int l = t[k].lc, r = t[k].rc;

	for(int i = 0; i < 2; ++i) {

		t[k].mi[i] = t[k].mx[i] = t[k].tp.x[i];

		if(l) t[k].mi[i] = min(t[k].mi[i], t[l].mi[i]), t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);

		if(r) t[k].mi[i] = min(t[k].mi[i], t[r].mi[i]), t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);

	}

	t[k].sum = t[l].sum + t[r].sum + t[k].tp.w, t[k].siz = t[l].siz + t[r].siz + 1;

}

int build(int l, int r, int wd) {

	if(l > r) return 0;

	int mid = (l + r) >> 1, k = newnode();

	WD = wd, nth_element(p + l, p + mid, p + r + 1), t[k].tp = p[mid];

	t[k].lc = build(l, mid - 1, wd ^ 1), t[k].rc = build(mid + 1, r, wd ^ 1);

	up(k); return k;

}

void pia(int k, int num) {

	if(t[k].lc) pia(t[k].lc, num);

	p[t[t[k].lc].siz + num + 1] = t[k].tp, rub[++top] = k;

	if(t[k].rc) pia(t[k].rc, num + t[t[k].lc].siz + 1);

}

void check(int &k, int wd) {

	if(0.75 * t[k].siz < t[t[k].lc].siz || 0.75 * t[k].siz < t[t[k].rc].siz)

		pia(k, 0), k = build(1, t[k].siz, wd);

}

void insert(int &k, poi tmp, int wd) {

	if(!k) { k = newnode(), t[k].lc = t[k].rc = 0, t[k].tp = tmp, up(k); return ; }

	if(tmp.x[wd] <= t[k].tp.x[wd]) insert(t[k].lc, tmp, wd ^ 1);

	else insert(t[k].rc, tmp, wd ^ 1);

	up(k), check(k, wd);

}

int in(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 out(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 k, int x1, int y1, int x2 ,int y2) {

	if(!k) return 0;

	int ret = 0;

	if(in(x1, y1, x2, y2, t[k].mi[0], t[k].mi[1], t[k].mx[0], t[k].mx[1])) return t[k].sum;

	if(out(x1, y1, x2, y2, t[k].mi[0], t[k].mi[1], t[k].mx[0], t[k].mx[1])) return 0;

	if(in(x1, y1, x2, y2, t[k].tp.x[0], t[k].tp.x[1], t[k].tp.x[0], t[k].tp.x[1])) ret += t[k].tp.w;

	return ret + query(t[k].lc, x1, y1, x2, y2) + query(t[k].rc, x1, y1, x2, y2);

}

int main () {

	read(n);

	while(true) {

		int opt; read(opt);

		if(opt == 3) break;

		else {

			read(x1), read(y1), x1 ^= ans, y1 ^= ans;

			if(opt == 1) read(k), insert(rt, (poi){x1, y1, k ^ ans}, 0);

			else {

				read(x2), read(y2), x2 ^= ans, y2 ^= ans;

				ans = query(rt, x1, y1, x2, y2), printf("%d\n", ans);

			}

		}

	}

    return 0;

}

巴特西

Luogu P4148 简单题（K-D Tree)

题面

题解

最新文章

热门文章