巧克力王国
巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。
对于每一块巧克力，我们设 x 和 y 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数 a 和 b ，分别为他自己为牛奶和可可定义的权重， 因此牛奶和可可含量分别为 x 和 y 的巧克力对于他的甜味程度即为 ax+by。而每个人又有一个甜味限度 c ，所有甜味程度大于等于 c 的巧克力他都无法接受。每块巧克力都有一个美味值 h 。
现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。
CQzhangyu的题解
看起来ax+by<c挺难搞，但其实只要改一改KDtree的估价函数就好了，具体见代码
其实就是判断一下矩形的四个角是否在半平面内。
注意：别忘了a,b,x,y可以是负数，负负能得正！
据说复杂度是每次询问期望√n，但我感觉这东西不靠谱。
struct kd{
int ls,rs,sm[2],sn[2],v[2];
ll sum,s;
kd(){}
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;}
}t[100001];
int n,m,D,root;
ll A,B,C;
bool cmp(co kd&a,co kd&b){
return a.v[D]<b.v[D];
}
void pushup(int x,int y){
for(int i=0;i<2;++i)
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 re=0;
re+=A*t[x].sn[0]+B*t[x].sn[1]<C;
re+=A*t[x].sm[0]+B*t[x].sn[1]<C;
re+=A*t[x].sm[0]+B*t[x].sm[1]<C;
re+=A*t[x].sn[0]+B*t[x].sm[1]<C;
return re;
}
ll query(int x){
if(!x||!check(x)) return 0;
if(check(x)==4) return t[x].sum;
ll re=0;
if(A*t[x].v[0]+B*t[x].v[1]<C) re+=t[x].s;
re+=query(t[x].ls)+query(t[x].rs);
return re;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
int a,b,c;
for(int i=1;i<=n;++i){
read(a),read(b),read(c);
t[i]=kd(a,b,c);
}
root=build(1,n,0);
for(int i=1;i<=m;++i){
read(A),read(B),read(C);
printf("%lld
",query(root));
}
return 0;
}