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。

Source

好久没写KDtree了，听取WA声一片。

本题其实就是一条直线下的所有点权和(ax + by < c)。可以用KDtree进行统计，当管辖区域全部在直线下方时返回，在直线上方时忽略，在直线中间时我们进入该子树继续递归。这样就能过了。（注意：一定要判断区间的四个端点，只判断两个端点会WA）

#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int maxn = 5e5 + 5;
int D, n, m, a, b, c;
struct Point {int v[2];};
struct WPoint {
	Point pos;
	int h;
}p[maxn];
bool cmp(const WPoint &p1, const WPoint &p2) {
	return p1.pos.v[D] < p2.pos.v[D];
}
namespace KD_tree {
	struct node {
		int ch[2], d, fa, h;
		LL sum;
		Point mn, mx, p;
	}tree[maxn];
	int cnt, root;
	#define pow(x) ((x) * (x))
	#define R 1
	#define L 0
	void push_up(int rt) {
		for(register int i = 0; i <= 1; ++i)
			if(tree[rt].ch[i]) {
				int son = tree[rt].ch[i];
				tree[rt].sum += tree[son].sum;
				for(register int j = 0; j <= 1; ++j) {
					tree[rt].mn.v[j] = min(tree[son].mn.v[j], tree[rt].mn.v[j]);
					tree[rt].mx.v[j] = max(tree[son].mx.v[j], tree[rt].mx.v[j]);
				}
			}
	}
	double Varience(int l, int r, int t) {
		double avr = 0, V = 0;
		int n = (r - l + 1);
		for(register int i = l; i <= r; ++i)
			avr += p[i].pos.v[t];
		avr /= n;
		for(register int i = l; i <= r; ++i)
			V += pow(p[i].pos.v[t] - avr) / n;
		return V;
	}
	void build(int & rt, int l, int r, int fa) {
		rt = ++cnt;
		if(l == r) {
			tree[rt].p = p[l].pos, tree[rt].sum = p[l].h;
			tree[rt].mn = tree[rt].mx = p[l].pos;
			return ;
		}
		int mid = l + r >> 1;
		double vx = Varience(l, r, 0), vy = Varience(l, r, 1);
		tree[rt].d = D = vx < vy;
		nth_element(p + l, p + mid, p + r + 1, cmp);
		tree[rt].fa = fa, tree[rt].sum = tree[rt].h = p[mid].h;
		tree[rt].p = p[mid].pos, tree[rt].mn = tree[rt].mx = tree[rt].p;
		if(l < mid) build(tree[rt].ch[L], l, mid - 1, rt);
		if(r > mid) build(tree[rt].ch[R], mid + 1, r, rt);
		push_up(rt);
	}
	bool under(LL a, LL b, LL c, Point mn, Point mx) {
		if(a * mn.v[0] + b * mx.v[1] >= c) return 0;
		if(a * mx.v[0] + b * mx.v[1] >= c) return 0;
		if(a * mn.v[0] + b * mn.v[1] >= c) return 0;
		if(a * mx.v[0] + b * mn.v[1] >= c) return 0;
		return 1;
	}
	bool over(LL a, LL b, LL c, Point mn, Point mx) {
		if(a * mn.v[0] + b * mn.v[1] <= c) return 0;
		if(a * mx.v[0] + b * mn.v[1] <= c) return 0;
		if(a * mn.v[0] + b * mx.v[1] <= c) return 0;
		if(a * mx.v[0] + b * mx.v[1] <= c) return 0;
		return 1;
	}
	LL query(int rt, LL a, LL b, LL c) {
		LL ret = 0;
		if((tree[rt].p.v[0] * a + tree[rt].p.v[1] * b) < c) 
			ret += tree[rt].h;
		for(int i = 0; i < 2; ++i) {
			if(!tree[rt].ch[i]) continue;
			node *son = &tree[tree[rt].ch[i]];
			if(under(a, b, c, son -> mn, son -> mx)) ret += son -> sum;
			else if(!(over(a, b, c, son -> mn, son -> mx)))
				ret += query(tree[rt].ch[i], a, b, c);
		}
		return ret;
	}
}
int main() {
	using namespace KD_tree;
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= n; ++i)
		scanf("%d%d%d", &p[i].pos.v[0], &p[i].pos.v[1], &p[i].h);
	build(root, 1, n, 0);
	while(m--) {
		scanf("%lld%lld%lld", &a, &b, &c);
		printf("%lld\n", query(1, a, b, c));
	}
	return 0;
}

Rockdu's Blog