bzoj 2850: 巧克力王国 （KD-tree）

2850: 巧克力王国

Time Limit: 60 Sec   Memory Limit: 512 MB
Submit: 504   Solved: 203
[ Submit][ Status][ Discuss]

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

Violet 0

[ Submit][ Status][ Discuss]

题解：KD-tree

这道题其实算是暴力吧，据说期望的时间复杂度是O(nsqrt(n))

就是一个区间内的点都符合要求，就加上计算区间的答案，如果有部分点符合要求就向下递归。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100003
#define LL long long
using namespace std;
struct data {
LL d[2],mn[2],mx[2];
int l,r;
LL val,sum;
}tr[N];
int root,n,m,cmpd;
LL ans,c,a,b;
int read()  
{  
    char c=getchar();  
    for (;c>'9'||c<'0';c=getchar());  
    int num=0;  
    for (;c>='0'&&c<='9';c=getchar())    
     num=num*10+c-'0';  
    return num;  
}  
int cmp(data a,data b)
{
return a.d[cmpd]<b.d[cmpd]||a.d[cmpd]==b.d[cmpd]&&a.d[cmpd^1]<b.d[cmpd^1];
}
void update(int now)
{
int l=tr[now].l; int r=tr[now].r;
for (int i=0;i<=1;i++){
if (l) tr[now].mx[i]=max(tr[now].mx[i],tr[l].mx[i]),
       tr[now].mn[i]=min(tr[now].mn[i],tr[l].mn[i]);
if (r) tr[now].mx[i]=max(tr[now].mx[i],tr[r].mx[i]),
       tr[now].mn[i]=min(tr[now].mn[i],tr[r].mn[i]);
}
if (l) tr[now].sum+=tr[l].sum;
if (r) tr[now].sum+=tr[r].sum;
}
int build(int l,int r,int d)
{
cmpd=d;
int mid=(l+r)/2;
nth_element(tr+l,tr+mid,tr+r+1,cmp);
for (int i=0;i<=1;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].d[i];
tr[mid].sum=tr[mid].val;
if (l<mid) tr[mid].l=build(l,mid-1,d^1);
if (r>mid) tr[mid].r=build(mid+1,r,d^1);
update(mid);
//cout<<tr[mid].d[0]<<" "<<tr[mid].d[1]<<" "<<tr[mid].sum<<endl;
return mid;
}
int check(int now)
{
int t=0;
if (!now) return 0;
t+=(tr[now].mx[0]*a+tr[now].mx[1]*b<c?1:0);
t+=(tr[now].mn[0]*a+tr[now].mn[1]*b<c?1:0);
t+=(tr[now].mx[0]*a+tr[now].mn[1]*b<c?1:0);
t+=(tr[now].mn[0]*a+tr[now].mx[1]*b<c?1:0);
return t;
}
void query(int now)
{
LL d0; int dl=0,dr=0;
d0=a*tr[now].d[0]+b*tr[now].d[1];
if (d0<c) ans+=tr[now].val;
dl=check(tr[now].l);
dr=check(tr[now].r);
//cout<<dl<<" "<<dr<<endl;
if (dl==4) ans+=tr[tr[now].l].sum;
  else if (dl) query(tr[now].l);
if (dr==4) ans+=tr[tr[now].r].sum;
  else if (dr)query(tr[now].r); 
}
int main()
{
freopen("a.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)  
 scanf("%I64d%I64d%I64d",&tr[i].d[0],&tr[i].d[1],&tr[i].val);
root=build(1,n,0);
for (int i=1;i<=m;i++) {
scanf("%I64d%I64d%I64d",&a,&b,&c);
ans=0;
query(root);
printf("%I64d\n",ans);
}
}