[BZOJ2850]巧克力王国

今天才学了一下kd-tree，感觉它本质上就是个暴力...

kd-tree用于维护高维空间中的一些点，它在建树时轮流在每一维坐标中选取中位数作为分割依据，最后形成一个树形结构

维护一个节点所管辖的坐标范围，然后查询就跟线段树差不多了

它维护$k$维空间时的范围查询时间复杂度是$O\left(kn^{1-\frac1k}\right)$，证明咕咕咕

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
struct candy{
	int x,y,h;
}d[50010];
struct kd{
	int l,r,mxx,mnx,mxy,mny,x,y,h;
	ll s;
	kd operator=(candy c){
		x=c.x;
		y=c.y;
		h=c.h;
		return*this;
	}
}t[50010];
bool cmpx(candy a,candy b){return a.x<b.x;}
bool cmpy(candy a,candy b){return a.y<b.y;}
void pushup(int x){
	t[x].mxx=t[x].mnx=t[x].x;
	t[x].mxy=t[x].mny=t[x].y;
	int l=t[x].l,r=t[x].r;
	if(l){
		t[x].mxx=max(t[x].mxx,t[l].mxx);
		t[x].mnx=min(t[x].mnx,t[l].mnx);
		t[x].mxy=max(t[x].mxy,t[l].mxy);
		t[x].mny=min(t[x].mny,t[l].mny);
	}
	if(r){
		t[x].mxx=max(t[x].mxx,t[r].mxx);
		t[x].mnx=min(t[x].mnx,t[r].mnx);
		t[x].mxy=max(t[x].mxy,t[r].mxy);
		t[x].mny=min(t[x].mny,t[r].mny);
	}
	t[x].s=t[l].s+t[r].s+t[x].h;
}
int build(int l,int r,int f){
	int mid=(l+r)>>1;
	nth_element(d+l,d+mid,d+r+1,f?cmpx:cmpy);
	t[mid]=d[mid];
	if(l<mid)t[mid].l=build(l,mid-1,f^1);
	if(mid<r)t[mid].r=build(mid+1,r,f^1);
	pushup(mid);
	return mid;
}
int a,b,c;
int check(ll x,ll y){return a*x+b*y<c;}
int check(kd u){return check(u.mnx,u.mny)+check(u.mxx,u.mny)+check(u.mnx,u.mxy)+check(u.mxx,u.mxy);}
ll query(int x){
	if(check(t[x])==4)return t[x].s;
	ll s=check(t[x].x,t[x].y)*t[x].h;
	if(check(t[t[x].l]))s+=query(t[x].l);
	if(check(t[t[x].r]))s+=query(t[x].r);
	return s;
}
int main(){
	int n,m,i,rt;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].h);
	rt=build(1,n,0);
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		printf("%lld\n",query(rt));
	}
}