BZOJ 2850: 巧克力王国(K-Dtree维护矩形中的点和)

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。

知道这个题考的是K-Dtree,就想怎么维护出来答案,发现没有动态插入点,那么就不需要替罪羊重建了,直接建树查询即可。K-Dtree每个节点都可以代表了一个矩形区域,我们知道这个节点所代表的矩形边界后,判断一下这个节点的矩形区域是否在ax+by=c这条直线以下,如果是的话直接返回节点维护的和,否则的话分别递归下去。但是不知道为什么我的查询一直T,不断卡常后还是卡不过去,于是就去看别人的写法,改成别人那样查询居然快了10倍??

感觉对这个东西还是不够熟练,每写一次就有很大的常数问题,所以需要进一步研究。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注