[BZOJ2850/Luogu4475]巧克力王国(KDT)

发布于 2018-05-15  78 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2850/Luogu4475]巧克力王国(KDT)

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜欢过于甜的巧克力。对于每一块巧克力,我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c,所有甜味程度大于等于c的巧克力他都无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少

Tag

KDT

解决思路

维护二维平面上的若干个点,每次查询这些点中符合要求的。用KDT优化暴力寻找。
需要注意的是,由于坐标和甜味程度都有可能是负数,所以要四个方向都判断一遍。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=51000;
const int inf=2147483647;

class KDT
{
public:
    ll sum,key;
    int ls,rs;
    ll P[2],Mx[2],Mn[2];
};

int n,m;
KDT T[maxN];
int nowD,root;

bool operator < (KDT A,KDT B);
int Build(int l,int r,int D);
void Update(int now);
ll Query(int now,ll a,ll b,ll c);

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld%lld%lld",&T[i].P[0],&T[i].P[1],&T[i].key);
    root=Build(1,n,0);
    for (int i=1;i<=m;i++)
    {
        ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);
        printf("%lld\n",Query(root,a,b,c));
    }
    return 0;
}

bool operator < (KDT A,KDT B){
    return A.P[nowD]<B.P[nowD];
}

int Build(int l,int r,int D)
{
    if (l>r) return 0;
    int mid=(l+r)>>1;
    nowD=D;
    nth_element(&T[l],&T[mid],&T[r+1]);
    T[mid].Mx[0]=T[mid].Mn[0]=T[mid].P[0];
    T[mid].Mx[1]=T[mid].Mn[1]=T[mid].P[1];
    T[mid].sum=T[mid].key;
    T[mid].ls=Build(l,mid-1,D^1);
    T[mid].rs=Build(mid+1,r,D^1);
    Update(mid);return mid;
}

void Update(int now)
{
    int ls=T[now].ls,rs=T[now].rs;
    T[now].sum=T[now].key;
    if (ls) T[now].sum+=T[ls].sum,T[now].Mn[0]=min(T[now].Mn[0],T[ls].Mn[0]),T[now].Mn[1]=min(T[now].Mn[1],T[ls].Mn[1]),T[now].Mx[0]=max(T[now].Mx[0],T[ls].Mx[0]),T[now].Mx[1]=max(T[now].Mx[1],T[ls].Mx[1]);
    if (rs) T[now].sum+=T[rs].sum,T[now].Mn[0]=min(T[now].Mn[0],T[rs].Mn[0]),T[now].Mn[1]=min(T[now].Mn[1],T[rs].Mn[1]),T[now].Mx[0]=max(T[now].Mx[0],T[rs].Mx[0]),T[now].Mx[1]=max(T[now].Mx[1],T[rs].Mx[1]);
    return;
}

ll Query(int now,ll a,ll b,ll c)
{
    int cnt=((T[now].Mn[0]*a+T[now].Mn[1]*b)<c)+((T[now].Mn[0]*a+T[now].Mx[1]*b)<c)+((T[now].Mx[0]*a+T[now].Mn[1]*b)<c)+((T[now].Mx[0]*a+T[now].Mx[1]*b)<c);
    if (cnt==0) return 0;
    if (cnt==4) return T[now].sum;
    ll Ret=0;
    if (T[now].P[0]*a+T[now].P[1]*b<c) Ret+=T[now].key;
    if (T[now].ls) Ret+=Query(T[now].ls,a,b,c);
    if (T[now].rs) Ret+=Query(T[now].rs,a,b,c);
    return Ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2850/Luogu4475]巧克力王国(KDT)


HNCJ OIer 一枚