BZOJ 2850: 巧克力王国

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

Solution

K-D Tree模板题。

本题中切割方式可以用方差来切割，因为本题比较特殊（维数=2）那么我们可以旋转着切割（横着来一刀，竖着来一刀）。询问时只有相交的时候才能继续询问左右孩子，否则不询问。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
struct MagHSK {
	int d[2], mx[2], mi[2], l, r, v;
	LL sum;
	int& operator[] (int x) { return d[x]; }
} p[50005], tree[50005];
int A, B, C, D;
bool operator < (MagHSK a, MagHSK b) { return a[D] < b[D]; }
int n, m;
void pu(int now) {
	int l = tree[now].l, r = tree[now].r;
	for (int i = 0; i < 2; ++i) {
		tree[now].mx[i] = tree[now].mi[i] = tree[now][i];
		if (l) {
			tree[now].mx[i] = max(tree[l].mx[i], tree[now].mx[i]);
			tree[now].mi[i] = min(tree[l].mi[i], tree[now].mi[i]);
		}
		if (r) {
			tree[now].mx[i] = max(tree[r].mx[i], tree[now].mx[i]);
			tree[now].mi[i] = min(tree[r].mi[i], tree[now].mi[i]);
		}
	}
	tree[now].sum = tree[l].sum + tree[r].sum + tree[now].v;
}
int build(int l, int r, int fs) {
	D = fs;
	int mid = (l + r) >> 1;
	nth_element(p+l, p+mid, p+r+1);
	tree[mid] = p[mid];
	if (l < mid) tree[mid].l = build(l, mid - 1, fs^1);
	if (r > mid) tree[mid].r = build(mid + 1, r, fs^1);
	pu(mid);
	return mid;
}
int check(int x, int y) { return (A*x+B*y<C); }
int calc(MagHSK &now) {
	return check(now.mx[0], now.mx[1])
		 + check(now.mx[0], now.mi[1])
		 + check(now.mi[0], now.mx[1])
		 + check(now.mi[0], now.mi[1]);
}
LL ans;
void query(int now) {
	int l = tree[now].l, r = tree[now].r;
	if (check(tree[now][0], tree[now][1])) ans += tree[now].v;
	int K;
	if (l) {
		K = calc(tree[l]);
		if (K == 4) ans += tree[l].sum;
		else { if (K) query(tree[now].l); }
	}
	if (r) {
		K = calc(tree[r]);
		if (K == 4) ans += tree[r].sum;
		else { if (K) query(tree[now].r); }
	}
}
int main() {
	n = getint(); m = getint();
	int a, b, c;
	for (int i = 1; i <= n; ++i) {
		p[i][0] = getint();
		p[i][1] = getint();
		p[i].v = getint();
	}
	int root = build(1, n, 0);
	while (m --) {
		A = getint(); B = getint(); C = getint();
		ans = 0;
		query(root);
		printf("%lld\n", ans);
	}
    return 0;
}