萌新求调 KDTree,2345WA
  • 板块P4148 简单题
  • 楼主fjy666
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/6/30 13:50
  • 上次更新2023/10/27 22:17:49
查看原帖
萌新求调 KDTree,2345WA
366338
fjy666楼主2022/6/30 13:50

rt,不带重构,理论上应该很好调/kk

//Code by fjy666
//luogu-judger-enable-O2
#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = a_; i_ <= b_; ++i_)
#define mid ((L+R) >> 1)
#define get(x) (((x) - 1) / kb + 1)
#define multiCase() int testCnt = in(); _rep(curCase,1,testCnt)
typedef long long ll;

int in(void) { int x; scanf("%d", &x); return x; }
ll inl(void) { ll x; scanf("%lld", &x); return x; }
template<typename T> void chkmax(T &a, const T &b) { a = max(a, b); } 
template<typename T> void chkmin(T &a, const T &b) { a = min(a, b); } 
const int kN = 500500;
const double alpha = 0.6114514; //magic constent
mt19937 engine((unsigned) time(nullptr));

int rt;
namespace KDTree {
	int x[kN], y[kN], sm[kN], l[kN], r[kN], u[kN], d[kN], v[kN], nc, ch[kN][2];
	void pushup(int rt) {
		#define upd(c) l[rt] = min(l[rt], l[c]), r[rt] = max(r[rt], r[c]), u[rt] = max(u[rt], u[c]), d[rt] = min(d[rt], d[c])
		l[rt] = r[rt] = x[rt], u[rt] = d[rt] = y[rt];
		if(ch[rt][0]) upd(ch[rt][0]); if(ch[rt][1]) upd(ch[rt][1]);
		sm[rt] = sm[ch[rt][0]] + sm[ch[rt][1]] + v[rt];
	}

	void insert(int &rt, int nx, int ny, int nv) { //calm down
		if(!rt) { rt = ++nc, x[nc] = nx, y[nc] = ny, v[nc] = nv, d[nc] = engine() % 2; }
		else {
			if(d[rt] == 0) insert(ch[rt][nx >= x[rt]], nx, ny, nv);
			else insert(ch[rt][ny >= y[rt]], nx, ny, nv);
		}
		pushup(rt);
	}

	//Query part
	//接受两个长方形,判断前者是否在后者内
	bool inRect(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;
	}
	//接受两个长方形,判断前者是否在后者外(指没有交点)
	bool outRect(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) {
		return (x2 < X1 || x1 > X2) || (y2 < Y1 || y1 > Y2);
	}
	int query(int o, int x1, int y1, int x2, int y2) {
		if(!o) return 0;
		if(inRect(l[o], u[o], r[o], d[o], x1, y1, x2, y2)) return sm[o];
		if(outRect(l[o], u[o], r[o], d[o], x1, y1, x2, y2)) return 0;
		int res = 0; if(inRect(x[o], y[o], x[o], y[o], x1, y1, x2, y2)) res += v[o];
		res += query(ch[o][0], x1, y1, x2, y2) + query(ch[o][1], x1, y1, x2, y2);
		return res;
	}
} //namespace KDTree

int lastans;
int main() { 
	in();
	int opt = in();
	while(opt != 3) {
		if(opt == 1) {
			int x = in() ^ lastans, y = in() ^ lastans, a = in() ^ lastans;
			KDTree::insert(rt, x, y, a);
		} else {
			int x1 = in() ^ lastans, y1 = in() ^ lastans, x2 = in() ^ lastans, y2 = lastans ^ in();
			printf("%d\n", lastans = KDTree::query(rt, x1, y1, x2, y2));
		}
		opt = in();
	}
	return 0;
}
2022/6/30 13:50
加载中...