BZOJ_2850_巧克力王国

BZOJ_2850_巧克力王国_KDTree

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。

正解不是KdTree，这玩意非矩形查询的复杂度好像是O(n^2)的。

不过这题可以做。

直接判矩形四个点是否都被包含/都不被包含即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 50050
#define ls ch[p][0]
#define rs ch[p][1]
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)>(y)?(x):(y))
int ch[N][2],mx[N][2],mn[N][2],n,root,m,now;
ll sum[N];
struct Point {
	int p[2],v;
	bool operator < (const Point &x) const {
		return p[now]==x.p[now]?p[!now]<x.p[!now]:p[now]<x.p[now];
	}
}a[N];
void pushup(int p,int x) {
	mx[p][0]=_max(mx[p][0],mx[x][0]);
	mn[p][0]=_min(mn[p][0],mn[x][0]);
	mx[p][1]=_max(mx[p][1],mx[x][1]);
	mn[p][1]=_min(mn[p][1],mn[x][1]);
	sum[p]+=sum[x];
}
int build(int l,int r,int type) {
	int mid=(l+r)>>1; now=type;
	nth_element(a+l,a+mid,a+r+1);
	mn[mid][0]=mx[mid][0]=a[mid].p[0];
	mn[mid][1]=mx[mid][1]=a[mid].p[1];
	sum[mid]=a[mid].v;
	if(l<mid) ch[mid][0]=build(l,mid-1,!type),pushup(mid,ch[mid][0]);
	if(r>mid) ch[mid][1]=build(mid+1,r,!type),pushup(mid,ch[mid][1]);
	return mid;
}
int check(ll x,ll y,ll z,int p) {
	return (x*mn[p][0]+y*mn[p][1]<z)+(x*mx[p][0]+y*mn[p][1]<z)+(x*mn[p][0]+y*mx[p][1]<z)+(x*mx[p][0]+y*mx[p][1]<z);
}
ll query(ll x,ll y,ll z,int p) {
	int tmp=check(x,y,z,p);
	if(!tmp) return 0;
	if(tmp==4) return sum[p];
	ll re=0;
	if(1ll*x*a[p].p[0]+1ll*y*a[p].p[1]<z) re+=a[p].v;
	if(ls) re+=query(x,y,z,ls);
	if(rs) re+=query(x,y,z,rs);
	return re;
}
int main() {
	scanf("%d%d",&n,&m);
	int i;
	ll x,y,z;
	for(i=1;i<=n;i++) {
		scanf("%d%d%d",&a[i].p[0],&a[i].p[1],&a[i].v);
	}
	root=build(1,n,0);
	for(i=1;i<=m;i++) {
		scanf("%lld%lld%lld",&x,&y,&z);
		printf("%lld
",query(x,y,z,root));
	}
}