巧克力王国

Time Limit: 60 Sec Memory Limit: 512 MB

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。

Main idea

每个点(x,y)以及价值，对于每个询问给定A,B,C。对于一个点，若Ax+By<C则可以获得该点的价值，问每个点可以得到的价值总和。

Solution

看到这种在平面上的题，我们显然想到了KD-tree。

因为可以离线，所以我们可以直接在建树的时候运用nth_element函数让它平衡。

对于每个点记录子树的最大最小的x与y以及总价值，然后KD-tree建树建完之后，查询的时候，如果所有情况都<C，我们就可以直接取走这个子树里面所有的值，如果存在可能的可能性就往下走。

PS：nth_element: 将一段序列从中间分开，给定的一个值放在中间(我们取中间的值即可)，剩下两边排放，效率O(n) 。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE=1000001;
const int INF=2147483640;

int n,m;
int x,y,A,B;
s64 C,h;
int root;
s64 Ans;
int Ran;

struct power
{
    int x,y,l,r;
    int maxx,maxy;
    int minx,miny;
    s64 val,sum;
}a[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

namespace KD
{
    void Update(int i)
    {
        a[i].sum=a[i].val;
        if(a[i].l)
        {
            a[i].sum+=a[a[i].l].sum;
            a[i].minx=min(a[i].minx,a[a[i].l].minx);    a[i].miny=min(a[i].miny,a[a[i].l].miny);
            a[i].maxx=max(a[i].maxx,a[a[i].l].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].l].maxy);
        }
        if(a[i].r)
        {
            a[i].sum+=a[a[i].r].sum;
            a[i].minx=min(a[i].minx,a[a[i].r].minx);    a[i].miny=min(a[i].miny,a[a[i].r].miny);
            a[i].maxx=max(a[i].maxx,a[a[i].r].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].r].maxy);
        }
    }

    int cmp(const power &a,const power &b)
    {
        if(Ran) return a.x<b.x; return a.y<b.y;
    }

    int Build(int l,int r,int T)
    {
        int mid=(l+r)/2;
        Ran=T;
        nth_element(a+l,a+mid,a+r+1,cmp);
        if(l<mid) a[mid].l = Build(l,mid-1,T^1);
        if(mid<r) a[mid].r = Build(mid+1,r,T^1);
        Update(mid);
        return mid;
    }
}

int PD(int x,int y)
{
    return (s64)A*x+(s64)B*y < C ;
}

int Check(int i)
{
    int res=0;
    res+= PD(a[i].minx,a[i].miny);
    res+= PD(a[i].minx,a[i].maxy);
    res+= PD(a[i].maxx,a[i].miny);
    res+= PD(a[i].maxx,a[i].maxy);
    return res;
}

void Query(int i)
{
    if(PD(a[i].x,a[i].y)) Ans+=a[i].val;
    if(a[i].l)
    {
        int Record=Check(a[i].l);
        if(Record==4) Ans+=a[a[i].l].sum;
        else if(Record) Query(a[i].l);
    }
    if(a[i].r)
    {
        int Record=Check(a[i].r);
        if(Record==4) Ans+=a[a[i].r].sum;
        else if(Record) Query(a[i].r);
    }
}


int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++) a[i].minx=a[i].miny=INF;
    for(int i=1;i<=n;i++)
    {
        x=get();    y=get();    scanf("%lld",&h);
        a[i].val=h;
        a[i].x=a[i].minx=a[i].maxx=x;
        a[i].y=a[i].miny=a[i].maxy=y;
    }
    root=KD::Build(1,n,1);

    while(m--)
    {
        A=get();    B=get();    scanf("%lld",&C);
        Ans=0;
        Query(root);
        printf("%lld\n",Ans);
    }
}