首页 > 代码库 > 【bzoj2850】巧克力王国 KD-tree

【bzoj2850】巧克力王国 KD-tree

2024-10-16 00:01:39   215人阅读

题目描述

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。对于每一块巧克力，我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少

输入

第一行两个正整数n和m，分别表示巧克力个数和询问个数。接下来n行，每行三个整数x,y,h，含义如题目所示。再接下来m行，每行三个整数a,b,c，含义如题目所示。

输出

输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

样例输入

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

样例输出

5
0
4

题解

KD-tree

朴素的n^2暴力显然会TLE，我们来优化这个过程。

题目要求出某条直线下方的所有点的权值和，不过看做直线并没有什么用。

考虑，如果能够使得某一些点都符合条件或都不符合条件，那么就可以降低查找的时间。

所以我们使用KD-tree来维护平面上的点。查询时，判断一下区域内的点是否都满足条件或都不满足条件，可以减去大量时间。

不过时间复杂度上界貌似还是O(n^2)的

估价函数需要分4种情况讨论

#include <cstdio>#include <algorithm>#define N 50010using namespace std;typedef long long ll;struct data{	ll p[2] , v , maxn[2] , minn[2] , sum;	int c[2];}a[N];int d , root;bool cmp(data a , data b){	return a.p[d] == b.p[d] ? a.p[d ^ 1] < b.p[d ^ 1] : a.p[d] < b.p[d];}void pushup(int k , int x){	a[k].maxn[0] = max(a[k].maxn[0] , a[x].maxn[0]);	a[k].maxn[1] = max(a[k].maxn[1] , a[x].maxn[1]);	a[k].minn[0] = min(a[k].minn[0] , a[x].minn[0]);	a[k].minn[1] = min(a[k].minn[1] , a[x].minn[1]);	a[k].sum += a[x].sum;}int build(int l , int r , int now){	int mid = (l + r) >> 1;	d = now , nth_element(a + l , a + mid , a + r + 1 , cmp);	a[mid].maxn[0] = a[mid].minn[0] = a[mid].p[0];	a[mid].maxn[1] = a[mid].minn[1] = a[mid].p[1];	a[mid].sum = a[mid].v;	if(l < mid) a[mid].c[0] = build(l , mid - 1 , now ^ 1) , pushup(mid , a[mid].c[0]);	if(r > mid) a[mid].c[1] = build(mid + 1 , r , now ^ 1) , pushup(mid , a[mid].c[1]);	return mid;}int getdis(int k , ll x , ll y , ll z){	if(x >= 0 && y >= 0)	{		if(x * a[k].maxn[0] + y * a[k].maxn[1] < z) return 1;		if(x * a[k].minn[0] + y * a[k].minn[1] >= z) return -1;	}	else if(x < 0 && y >= 0)	{		if(x * a[k].minn[0] + y * a[k].maxn[1] < z) return 1;		if(x * a[k].maxn[0] + y * a[k].minn[1] >= z) return -1;	}	else if(x >= 0 && y < 0)	{		if(x * a[k].maxn[0] + y * a[k].minn[1] < z) return 1;		if(x * a[k].minn[0] + y * a[k].maxn[1] >= z) return -1;	}	else	{		if(x * a[k].minn[0] + y * a[k].minn[1] < z) return 1;		if(x * a[k].maxn[0] + y * a[k].maxn[1] >= z) return -1;	}	return 0;}ll query(int k , ll x , ll y , ll z){	int t = getdis(k , x , y , z);	if(t == 1) return a[k].sum;	if(t == -1) return 0;	ll ans = 0;	if(a[k].p[0] * x + a[k].p[1] * y < z) ans += a[k].v;	if(a[k].c[0]) ans += query(a[k].c[0] , x , y , z);	if(a[k].c[1]) ans += query(a[k].c[1] , x , y , z);	return ans;}int main(){	int n , m , i;	ll x , y , z;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) scanf("%lld%lld%lld" , &a[i].p[0] , &a[i].p[1] , &a[i].v);	root = build(1 , n , 0);	while(m -- ) scanf("%lld%lld%lld" , &x , &y , &z) , printf("%lld\n" , query(root , x , y , z));	return 0;}

 

 

【bzoj2850】巧克力王国 KD-tree


联系
我们