bzoj 2850 巧克力王国

桃扇骨 2021-12-10 10:43 184阅读 0赞

## 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。

思路： kd树+启发式搜索，估计函数是$ax+by$，这个估计有点神奇，每次计算4个可能性，即当前区域x的最大值和最小值，区域y的最大值和最小值，和a，b进行配对计算。

如果全部4个都小于c，那么就直接累计sum，否则只要有1个以上，就去递归计算。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long   
     4 int const N=50000+10;  
     5 int n,m,cur,root;   
     6 struct P{
     7     ll   d[2],mx[2],mn[2],ch[2],v,sum;    
     8     ll & operator [] (int x){  return d[x];  } 
     9     friend bool operator  < ( P x,P y) {
    10         return x[cur]<y[cur];  
    11     }
    12 }p[N];  
    13 struct kdtree{
    14     P t[N],T;  
    15     ll  ans;  
    16     void update(int k){
    17         int l=t[k].ch[0]; 
    18         int r=t[k].ch[1]; 
    19         for(int i=0;i<2;i++){
    20             if(l)  t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]); 
    21             if(l)  t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);  
    22             if(r)  t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]); 
    23             if(r)  t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]); 
    24         }
    25         t[k].sum=t[k].v+t[l].sum+t[r].sum;     
    26     }
    27     int check(P x,ll c){
    28         int ret=0;  
    29         ret+=x.mn[0]*T[0]+x.mn[1]*T[1]<c;  
    30         ret+=x.mn[0]*T[0]+x.mx[1]*T[1]<c;  
    31         ret+=x.mx[0]*T[0]+x.mn[1]*T[1]<c;  
    32         ret+=x.mx[0]*T[0]+x.mx[1]*T[1]<c;  
    33         return ret;  
    34     }  
    35     int build(int l,int r,int now){
    36         cur=now;  
    37         int mid=(l+r)/2;  
    38         nth_element(p+l,p+mid,p+r+1);  
    39         t[mid]=p[mid];  
    40         for(int i=0;i<2;i++) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];  
    41         if(l<mid) t[mid].ch[0]=build(l,mid-1,now^1); 
    42         if(mid<r) t[mid].ch[1]=build(mid+1,r,now^1);  
    43         update(mid); 
    44         return mid; 
    45     } 
    46     void solve(int k,ll c,int now){
    47         if(T[0]*t[k][0]+T[1]*t[k][1]<c ) ans+=t[k].v;    
    48         int dl=0,dr=0;  
    49         int l=t[k].ch[0]; 
    50         int r=t[k].ch[1];  
    51         if(l) dl=check(t[l],c);  
    52         if(r) dr=check(t[r],c);  
    53         if(dl==4) ans+=t[l].sum;  
    54         else if(dl) solve(l,c,now^1);  
    55         if(dr==4) ans+=t[r].sum;  
    56         else if(dr) solve(r,c,now^1);  
    57     } 
    58     ll query(int a,int b,ll c){
    59         T[0]=a; T[1]=b;  
    60         ans=0; 
    61         solve(root,c,0); 
    62         return ans;  
    63     }       
    64 }kd;  
    65 int main(){
    66     scanf("%d%d",&n,&m);  
    67     for(int i=1;i<=n;i++)  
    68         scanf("%lld%lld%lld",&p[i][0],&p[i][1],&p[i].v);  
    69     root=kd.build(1,n,0);   
    70     while (m--){
    71         int a,b;  
    72         ll c;  
    73         scanf("%d%d%lld",&a,&b,&c); 
    74         printf("%lld\n",kd.query(a,b,c));  
    75     }
    76     return 0; 
    77 }

转载于:https://www.cnblogs.com/ZJXXCN/p/11131773.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211210/430a3bdd1c694cdab2f4018a23bdf0a0.png