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
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7
Sample Output
5
0
4
0
4
HINT
1 <= n, m <= 50000,1 <= 10^9,-10^9 <= a, b, x, y <= 10^9。
Source
Violet 0
KDtree+思路~
神奇的数形结合(?)思想!因为所有巧克力都有两个属性,所以我们把每一块巧克力都看做点,利用KDtree划分区间,我们可以快速查询。
当子树整个区间都满足ax+by<c时,我们就可以把这一块整个加入到答案中,这样可以减小查询次数。
(其实个人认为巧克力还是80%~90%的比较好~)
注意记录的区间和要开long long!
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;int n,m,root;
long long A,B,C,ans;
bool kkz;struct node{int a[2],mn[2],mx[2],v,l,r;long long num;
}a[50001],c[50001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}bool operator < (node u,node v)
{return u.a[kkz]<v.a[kkz];
}bool chec(int u,int v)
{return A*u+B*v<C;
}int cal(node u)
{int now=0;now+=chec(u.mn[0],u.mn[1]);now+=chec(u.mx[0],u.mx[1]);now+=chec(u.mn[0],u.mx[1]);now+=chec(u.mx[0],u.mn[1]);return now;
}void update(int u)
{node l=c[c[u].l],r=c[c[u].r];for(int i=0;i<2;i++){if(c[u].l) c[u].mn[i]=min(c[u].mn[i],l.mn[i]),c[u].mx[i]=max(c[u].mx[i],l.mx[i]);if(c[u].r) c[u].mn[i]=min(c[u].mn[i],r.mn[i]),c[u].mx[i]=max(c[u].mx[i],r.mx[i]);}c[u].num=c[u].v+l.num+r.num;
}int build(int l,int r,int now)
{int mid=l+r>>1;kkz=now;nth_element(a+l,a+mid,a+r+1);c[mid]=a[mid];for(int i=0;i<2;i++) c[mid].mn[i]=c[mid].mx[i]=c[mid].a[i];if(l<mid) c[mid].l=build(l,mid-1,now^1);if(r>mid) c[mid].r=build(mid+1,r,now^1);update(mid);return mid;
}void query(int u)
{int l=c[u].l,r=c[u].r;if(chec(c[u].a[0],c[u].a[1])) ans+=c[u].v;int dl=0,dr=0;if(l) dl=cal(c[l]);if(r) dr=cal(c[r]);if(dl==4) ans+=c[l].num;else if(dl) query(l);if(dr==4) ans+=c[r].num;else if(dr) query(r);
}int main()
{n=read();m=read();for(int i=1;i<=n;i++) a[i].a[0]=read(),a[i].a[1]=read(),a[i].v=read();root=build(1,n,0);for(int i=1;i<=m;i++){A=read();B=read();C=read();ans=0;query(root);printf("%lld\n",ans); }return 0;
}