省选-数据结构-K-D Tree · Zhl2010 第二博客

K-D Tree 是一种维护高维数据的数据结构，可以用于解决高维的问题。

优点：好写，思路简单
缺点：有的问题中复杂度是伪的。

基础题

P4475 巧克力王国

这道题我们发现这是一个式子：

ax+by\le c\\ by\le c-ax\\ y\le \frac{c}{b}-\frac{a}{b}x

所以我们相当于需要查询一条线一边的矩形。

于是我们需要修改我们的查询：

如果当前这个矩形全在这条线的这个方向（只需要判断四个顶点），直接计算贡献。
如果全不在，就停止。
部分在，就分治下去，这跟普通 K-D Tree 差不多。

注意，我们一半写的是非 Leaf Tree，也就是每个节点都有权值，我们询问不仅需要算 $ls$ 和 $rs$ 的，还需要算自己的。而且比如有懒标记，下穿的时候自己也需要加。

P14312 【模板】K-D Tree

P14312 【模板】K-D Tree。

这个就是模板了，其实没什么好说的，直接放代码。

代码

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,m,LG;
struct node{
	int z[4];
	int mn[4],mx[4],ls,rs;
	int val;
	int sum,sz;
	int tag;
}t[150010],L,R;
int Val;
int rt[150010],n=0,cnt=0;
#define mid (l+r>>1)
void pushup(int x){
	int L=t[x].ls,R=t[x].rs;
	for(int i=0;i<k;i++){
		t[x].mn[i]=min(t[x].z[i],min(t[L].mn[i],t[R].mn[i]));
		t[x].mx[i]=max(t[x].z[i],max(t[L].mx[i],t[R].mx[i]));
	}
	t[x].sum=t[L].sum+t[R].sum+t[x].val;
	t[x].sz=t[L].sz+t[R].sz+1;
}
void pushdown(int x){
	if(!t[x].tag)return;
	int L=t[x].ls,R=t[x].rs;
	if(L)t[L].tag+=t[x].tag,t[L].sum+=t[L].sz*t[x].tag,t[L].val+=t[x].tag;
	if(R)t[R].tag+=t[x].tag,t[R].sum+=t[R].sz*t[x].tag,t[R].val+=t[x].tag;
	t[x].tag=0;
}
int a[150010];
void release(int& x){
	if(!x)return;
	a[++n]=x;
	pushdown(x);
	release(t[x].ls),release(t[x].rs);
	x=0;
}
int build(int l,int r,int p){
	nth_element(a+l,a+mid,a+r+1,[p](int x,int y){return t[x].z[p]<t[y].z[p];});
	int x=a[mid];
	if(l<mid)t[x].ls=build(l,mid-1,(p+1)%k);
	if(r>mid)t[x].rs=build(mid+1,r,(p+1)%k);
	pushup(x);
	return x;
}
void modify(int x){ 
	if(!x)return;
	for(int i=0;i<k;i++)if(t[x].mx[i]<L.z[i]||t[x].mn[i]>R.z[i])return;
	int pd=1;
	for(int i=0;i<k;i++)if(!(t[x].mx[i]<=R.z[i]&&t[x].mn[i]>=L.z[i])){
		pd=0;break;
	}
	if(pd){
		t[x].val+=Val;
		t[x].sum+=Val*t[x].sz;
		t[x].tag+=Val;
		return;
	}
	pd=1;
	for(int i=0;i<k;i++)if(!(t[x].z[i]<=R.z[i]&&t[x].z[i]>=L.z[i])){
		pd=0;break;
	}
	if(pd)t[x].val+=Val;
	pushdown(x);
	modify(t[x].ls),modify(t[x].rs);
	pushup(x);
}
int query(int x){
	if(!x)return 0;
	for(int i=0;i<k;i++)if(t[x].mx[i]<L.z[i]||t[x].mn[i]>R.z[i])return 0;
	int pd=1;
	for(int i=0;i<k;i++)if(!(t[x].mx[i]<=R.z[i]&&t[x].mn[i]>=L.z[i])){
		pd=0;break;
	}
	if(pd){
		return t[x].sum;
	}
	int res=0;
	pd=1;
	for(int i=0;i<k;i++)if(!(t[x].z[i]<=R.z[i]&&t[x].z[i]>=L.z[i])){
		pd=0;break;
	}
	if(pd)res=t[x].val;
	pushdown(x);
	return res+query(t[x].ls)+query(t[x].rs);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>k>>m;
	LG=log2(m)+1;
	for(int i=0;i<k;i++) t[0].mn[i]=1e18;
	for(int i=0;i<k;i++) t[0].mx[i]=0;
	int ans=0;
	for(int i=1;i<=m;i++){
		int op,v;
		cin>>op;
		if(op==1){
			++cnt;
			for(int j=0;j<k;j++)cin>>t[cnt].z[j],t[cnt].z[j]^=ans;
			cin>>t[cnt].val;
			t[cnt].val^=ans;
			a[n=1]=cnt;
			for(int j=0;j<=LG;j++){
				if(!rt[j]){
					rt[j]=build(1,n,0);
					break;
				}else{
					release(rt[j]);
				}
			}
		}else if(op==2){
			for(int j=0;j<k;j++)cin>>L.z[j],L.z[j]^=ans;
			for(int j=0;j<k;j++)cin>>R.z[j],R.z[j]^=ans;
			cin>>Val;
			Val^=ans;
			for(int j=0;j<=LG;j++)modify(rt[j]);
		}else{
			for(int j=0;j<k;j++)cin>>L.z[j],L.z[j]^=ans;
			for(int j=0;j<k;j++)cin>>R.z[j],R.z[j]^=ans;
			ans=0;
			for(int j=0;j<=LG;j++)ans+=query(rt[j]);
			cout<<ans<<'\n';
		}
	}
	
	
	return 0;
}

K-D Tree 的剪枝

在有些问题中，K-D Tree 的复杂度是不正确的，为了防止被卡，我们需要加上一些剪枝，就是不去遍历一些位置。

我们可以配合上估价函数去写。

P2093 [国家集训队] JZPFAR

P2093 [国家集训队] JZPFAR。

注意到 $k$ 很小。

询问的时候，我们考虑用一个小根堆维护前 $k$ 小点，堆顶就是答案。

然后询问的话，我们就看 $l$ 与 $r$ ，从拥有最大的点的那个开始遍历。这样的话就可以避免掉很多没有必要的访问，能过。

P4631 [APIO2018] 选圆圈

P4631 [APIO2018] 选圆圈。

K-D Tree 很多时候可以用来乱搞过题，因为很多时候它的复杂度是伪的，但是加上“人类智慧”就行了。

我们看到这道题自然会想到 K-D Tree，但是这道题是圆，没办法直接维护，所以我们可以尝试暴力维护，然后剪枝。

怎么剪？我们可以考虑记录这个圆的矩形，然后利用两个圆的矩形是否相交进行剪枝。

然后再配合上旋转的人类智慧，就可以 AC 了。注意，eps 一定要用，有的时候判断不能是 = 的时候，需要往小的那一边 +eps。

最后我发现 eps 好像小了，改大就 A 了？1e-8=>1e-3。

P2479 [SDOI2010] 捉迷藏

P2479 [SDOI2010] 捉迷藏。

法一，按照斜率排序，然后取中间 $800$ 个，过了，很好写。怕被卡加个随机转。

法二：拆掉绝对值，然后用逆序对表示cdq 可以做。

法三，就是 K-D Tree 了。我们发现暴力去做肯定是错的，可以加上减枝。K-D Tree 上每一个点都代表一个矩阵，剪枝的时候我们就拿最极端的情况和当前答案比较就行了。能过的。

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95。

这道题是求逆序对数，但是它定义的不同是指的权值不同，不是下标。

所以我们可以记录每一个数第一次出现的位置，和最后一次出现的位置。

很多时候 cdq 也可以做这种偏序问题，只是是离线的。这道题 K-D Tree 好像可以做，但是没那么好写。

cdq

可以用差分思想，离线处理每一次修改的影响。

用五元组 $(x,y,0/1,t,k)$ 表示将 $x$ 的 $fst/ed$ 改成 $y$ ， $k$ 表示这是删除这个状态还是加入这个状态。

$(x,y,0,t,k)$ 的贡献是 $\displaystyle k \sum_{(x',y',1,t,k)}k[x' < x \wedge y' > y \wedge t'<t]$ 。

$(x,y,1,t,k)$ 的贡献是 $\displaystyle k \sum_{(x',y',0,t,k)}k[x' > x \wedge y' < y \wedge t'<t]$ 。

注意，只需要排一遍序，因为后面倒着枚举就行了。