首页 > 代码库 > 【BZOJ2850】巧克力王国 KDtree

【BZOJ2850】巧克力王国 KDtree

2024-09-28 04:06:38   218人阅读

【BZOJ2850】巧克力王国

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

5
0
4

HINT

1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

题解：看起来ax+by<=c挺难搞，但其实只要改一改KDtree的估价函数就好了，具体见代码

注意：别忘了a,b,x,y可以是负数，负负能得正！

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rep for(int i=0;i<=1;i++)using namespace std;typedef long long ll;struct kd{	int ls,rs,sm[2],sn[2],v[2];	ll sum,s;	kd (int a,int b,int c){ls=rs=0,sm[0]=sn[0]=v[0]=a,sm[1]=sn[1]=v[1]=b,s=sum=c;}	kd (){}};kd t[100010];int n,m,D,root;ll A,B,C;bool cmp(kd a,kd b){	return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);}void pushup(int x,int y){	rep	t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);	t[x].sum+=t[y].sum; }int build(int l,int r,int d){	if(l>r)	return 0;	int mid=l+r>>1;	D=d;	nth_element(t+l,t+mid,t+r+1,cmp);	t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);	if(t[mid].ls)	pushup(mid,t[mid].ls);	if(t[mid].rs)	pushup(mid,t[mid].rs);	return mid;}int check(int x){	int ret=0;	ret+=(A*t[x].sn[0]+B*t[x].sn[1]<C);	ret+=(A*t[x].sm[0]+B*t[x].sn[1]<C);	ret+=(A*t[x].sm[0]+B*t[x].sm[1]<C);	ret+=(A*t[x].sn[0]+B*t[x].sm[1]<C);	return ret;}ll query(int x){	if(!x||!check(x))	return 0;	if(check(x)==4)	return t[x].sum;	ll ret=0;	if(A*t[x].v[0]+B*t[x].v[1]<C)	ret+=t[x].s;	ret+=query(t[x].ls)+query(t[x].rs);	return ret;}int main(){	scanf("%d%d",&n,&m);	int i,a,b,c;	for(i=1;i<=n;i++)	{		scanf("%d%d%d",&a,&b,&c);		t[i]=kd(a,b,c);	}	root=build(1,n,0);	for(i=1;i<=m;i++)	{		scanf("%lld%lld%lld",&A,&B,&C);		printf("%lld\n",query(root));	}	return 0;}

 

【BZOJ2850】巧克力王国 KDtree


联系
我们