k-d Tree 20pts 求条
查看原帖
k-d Tree 20pts 求条
963247
Slient_QwQ楼主2024/4/13 15:25

rt

/*Code By Manipula*/
#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define fi first
#define sc second
#define lb lower_bound
#define YES printf("YES\n")
#define Yes printf("Yes\n")
#define NO printf("NO\n")
#define No printf("No\n")
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(fmt, arg...) fprintf(stderr, fmt, ##arg)
#define DEBUG() debug("In Function [%s] Line %d\n", __FUNCTION__, __LINE__) 

const int N = 5e5 + 5;
const double alpha = 0.75;

struct Point {
	int x[2], val;
} a[N];

int fr[N];
int n, rt, tot, cnt, top, lstAns;

namespace KD_Tree {
	struct Node {
		int ls, rs, L[2], R[2], sum, siz;
		Point P;
		
		#define ls(p) (tr[p].ls)
		#define rs(p) (tr[p].rs)
	} tr[N];
	
	void init() {
		tr[0].L[0] = tr[0].L[1] = INF;
		tr[0].R[0] = tr[0].R[1] = -INF;
	}
	
	void pushup(int p) {
		auto L = tr[ls(p)], R = tr[rs(p)];
		
		tr[p].sum = tr[p].P.val + L.sum + R.sum;
		tr[p].siz = L.siz + R.siz + 1;
		
		for (int i = 0; i <= 1; i++) {			
			tr[p].L[i] = std::min(tr[p].P.x[i], L.L[i]);
			tr[p].R[i] = std::max(tr[p].P.x[i], R.R[i]);
		}
	}
	
	int Add() { return !top ? ++tot : fr[top--]; }
	
	int Rebuild(int l, int r, int D) {
		if (l > r)return 0;
		int mid = (l + r) >> 1;
		int p = Add();
		
		std::nth_element(a + l, a + mid, a + r + 1, [&](Point A, Point B) { return A.x[D] < B.x[D]; });
		tr[p].P = a[mid];
		
		ls(p) = Rebuild(l, mid - 1, D ^ 1);
		rs(p) = Rebuild(mid + 1, r, D ^ 1);
		pushup(p);
		
		return p;
	}
	
	void slap(int p) {
		if (!p)return;
		
		slap(ls(p));
		fr[++top] = p, a[++cnt] = tr[p].P;
		slap(rs(p));
	}
	
	void Work(int &p, int D) {
		if (tr[p].siz * alpha <= tr[ls(p)].siz || tr[p].siz * alpha <= tr[rs(p)].siz)
			cnt = 0, slap(p), p = Rebuild(1, tr[p].siz, D);
	}
	
	void Insert(int &p, Point P, int D) {
		if (!p)return p = Add(), ls(p) = rs(p) = 0, tr[p].P = P, pushup(p);
		
		if (P.x[D] <= tr[p].P.x[D])Insert(ls(p), P, D ^ 1);
		else Insert(rs(p), P, D ^ 1);
		
		pushup(p);
		Work(p, D);
	}
	
	int Query(int p, int x1, int y1, int x2, int y2) {
		if (!p)return 0;
		
		if (x1 <= tr[p].L[0] && tr[p].R[0] <= x2 && y1 <= tr[p].L[1] && tr[p].R[1] <= y2)
			return tr[p].sum;
		
		if (tr[p].L[0] < x1 || tr[p].R[0] > x2 || tr[p].L[1] < y1 || tr[p].R[1] > y2)
			return 0;
		
		int ans = 0;
		if (x1 <= tr[p].P.x[0] && tr[p].P.x[0] <= x2 && y1 <= tr[p].P.x[1] && tr[p].P.x[1] <= y2)
			ans += tr[p].P.val;
		
		ans += Query(ls(p), x1, y1, x2, y2) + Query(rs(p), x1, y1, x2, y2);
		
		return ans;
	}
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	
	int opt;
	
	scanf("%d", &n);
	
	KD_Tree::init();
		
	while (scanf("%d", &opt), opt != 3) {
		if (opt == 1) {
			int x, y, k; scanf("%d%d%d", &x, &y, &k);
			x ^= lstAns, y ^= lstAns, k ^= lstAns;
			
			KD_Tree::Insert(rt, (Point){x, y, k}, 0);
		}
		else {
			int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			x1 ^= lstAns, x2 ^= lstAns, y1 ^= lstAns, y2 ^= lstAns;
			
			printf("%d\n", lstAns = KD_Tree::Query(rt, x1, y1, x2, y2));
		}
	}
	
	return 0;
}
2024/4/13 15:25
加载中...