KD-Tree

KD-Tree存储多维偏序十分方便
至于这个树是怎样的呢，我们可以看看。
例如，一个二维KD-Tree。
显然我们每个节点要存储自己的信息，设这个数组为val[2]。（可以理解为val[0]存x，val[1]存y）
显然，需要放进一个二叉搜索树中查询比较方便。那么，到底应该按照什么关键字排序呢？
这里是KD-Tree的核心思想，例如二维KD-Tree根是第零层，那么第一层就按照第一维排序，第二层就按照第二维排序，第三层按回第一位排序，这样往复循环。
同理，如果是三维的话就1,2,3维这样按层依次排序，如此即可。
然后，用替罪羊树使其保持平衡，深度就保持在$log(n)$log(n)的啦。
需要注意的一点是，我打了一年的替罪羊树都是在$query$query的时候$check$check的
没想到大多数人的写法是在$insert$insert的时候$check$check的。这样写确实更方便，但是似乎最差复杂度要高？
但是均摊下来，复杂度差不多，常数要小呢。

看一个例题吧

【BZOJ4066】简单题

显然这一题如果可以离线可以用CDQ做，但是显然不能离线，我也早把CDQ忘光了。
所以我们用KD-Tree。
对于一个节点node，我们除了定义x[2]（坐标）和val（这个点的数字），还需要定义在它的子树中x值的最值与y值的最值。可以用ma[2]和mi[2]来存储。然后我们开一个sum，用来记录它子树中的数字和。

于是这个点的x最值和y最值（包括最大值和最小值）共同形成了一个矩形。

查询的时候，如果这个矩形在查询矩阵内部，答案加当前节点的sum，走人。
如果有部分相交，就搜下去，如果没有相交，就直接走人，反正这个子树内没有对答案有贡献的。

那么，加的操作呢。我们可以考虑，每对于节点(x, y)加上A，就打包成val=A的节点丢进树中，查询时能够查到偶。如果树中已经有(x,y)也不会影响，处理答案时两个树中节点都会加上的。

这个故事告诉我们，KD-Tree就是一个无脑暴力。

贴代码

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;
const double alpha=0.75;

int read() {
	int q=0,w=1;
	char ch=' ';
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1,ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q*w;
}

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

struct node {
	int ma[2], mi[2], ls, rs, siz, sum;
	point po;
} a[N];

int rec[N], cnt, top, flag;
int n, m;

bool operator <(point a, point b) {
	return a.x[flag]<b.x[flag];
}

int new_node() {
	return top?rec[top--]:++cnt;
}

void update(int x) {
	int l=a[x].ls, r=a[x].rs;
	for(int i=0; i<=1; i++) {
		a[x].ma[i]=a[x].mi[i]=a[x].po.x[i];
		if(l) a[x].ma[i]=max(a[x].ma[i], a[l].ma[i]), a[x].mi[i]=min(a[x].mi[i], a[l].mi[i]);
		if(r) a[x].ma[i]=max(a[x].ma[i], a[r].ma[i]), a[x].mi[i]=min(a[x].mi[i], a[r].mi[i]);
	}
	a[x].sum=a[l].sum+a[r].sum+a[x].po.w;
	a[x].siz=a[l].siz+a[r].siz+1;
}

int build(int l, int r, int nflag) {
	if(l>r) return 0;
	int mid=(l+r)>>1, x=new_node();
	flag=nflag;
	nth_element(w+l, w+mid, w+r+1);
	a[x].po=w[mid];
	a[x].ls=build(l, mid-1, !nflag);
	a[x].rs=build(mid+1, r, !nflag);
	update(x);
	return x;
}

void destory(int x, int pai) {
	if(a[x].ls) destory(a[x].ls, pai);
	pai+=a[a[x].ls].siz+1;
	w[pai]=a[x].po, rec[++top]=x;
	if(a[x].rs) destory(a[x].rs, pai);
}

void check(int &x, int nflag) {
	if((double)max(a[a[x].ls].siz, a[a[x].rs].siz)>a[x].siz*alpha) {
		destory(x, 0);
		x=build(1, a[x].siz, nflag);
	}
}

void ins(int &x, point po, int nflag) {
	if(!x) {
		x=new_node();
		a[x].ls=a[x].rs=0;
		a[x].po=po;
		update(x);
		return;
	}
	if(po.x[nflag]<a[x].po.x[nflag]) ins(a[x].ls, po, !nflag);
	else ins(a[x].rs, po, !nflag);
	update(x);
	check(x, nflag);
}

inline bool in(int qx1, int qy1, int qx2, int qy2, int X1, int Y1, int X2, int Y2) {
	return (X1>=qx1&&X2<=qx2&&Y1>=qy1&&Y2<=qy2);
}

inline bool out(int qx1,int qy1,int qx2,int qy2,int X1,int Y1,int X2,int Y2) {
	return (qx1>X2||qx2<X1||qy1>Y2||qy2<Y1);
}

int query(int x, int qx1, int qy1, int qx2, int qy2) {
	if(!x) return 0;
	int ans=0;
	if(in(qx1,qy1,qx2,qy2,a[x].mi[0],a[x].mi[1],a[x].ma[0],a[x].ma[1])) return a[x].sum;
	if(out(qx1,qy1,qx2,qy2,a[x].mi[0],a[x].mi[1],a[x].ma[0],a[x].ma[1])) return 0;
	if(in(qx1,qy1,qx2,qy2,a[x].po.x[0],a[x].po.x[1],a[x].po.x[0],a[x].po.x[1])) ans+=a[x].po.w;
	return ans+query(a[x].ls, qx1, qy1, qx2, qy2)+query(a[x].rs, qx1, qy1, qx2, qy2);
}

int rt;

int main() {
	int flag, ans=0, a, b, c, d;
	scanf("%d", &n);
	while(1) {
		scanf("%d", &flag);
		if(flag==1) {
			scanf("%d%d%d", &a, &b, &c);
			ins(rt, (point) {
				a^ans, b^ans, c^ans
			}, 0);
		}
		if(flag==2) {
			scanf("%d%d%d%d", &a, &b, &c, &d);
			printf("%d\n", ans=query(rt, a^ans, b^ans, c^ans, d^ans));
		}
		if(flag==3) break;
	}
	return 0;
}