【bzoj2850】巧克力王国

2015.06.17 18:07 Wed | 23次阅读 | 旧日oi | 固定链接 | 源码

题目大意,二维平面上给定一些点,每次给出A,B,C,询问有多少点满足A*X+B*Y<C,点数<=50000
题解:
把给定的点建成KDtree,然后处理询问的方法也和每次一样,只是估价函数不同,因为给定的关系式是线性的,所以如果边界都合法,那么内部的点也合法,通过这个我们可以剪枝掉一些估价函数为0的地方,并且估价函数为4的地方也可以不用算,因为边界都满足了,直接把那部分的sum加到ans里就行。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
#define N 50005
#define ls t[x].l
#define rs t[x].r
#define ll long long
int n,m,root,D;
ll ans,A,B,C;
struct node
{
    int l,r,mx[2],mn[2],pla[2];
    ll v,sum;
    int & operator [](int x){return pla[x];}
    bool operator <(const node &a)const{
        return pla[D]<a.pla[D];
    }
}p[N];
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f==1?x:-x;
}
struct KDT
{
    node t[N];
    void update(int x)
    {
        for(int i=0;i<2;i++)
        {
            if(ls) t[x].mn[i]=min(t[x].mn[i],t[ls].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[ls].mx[i]);
            if(rs) t[x].mn[i]=min(t[x].mn[i],t[rs].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[rs].mx[i]);
        }
        t[x].sum=t[ls].sum+t[x].v+t[rs].sum;
    }
    int build(int l,int r,int now)
    {
        D=now;
        int mid=(l+r)>>1;
        nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        for(int i=0;i<2;i++) t[mid].mx[i]=t[mid].mn[i]=t[mid][i];
        if(l<mid) t[mid].l=build(l,mid-1,now^1);
        if(mid<r) t[mid].r=build(mid+1,r,now^1);
        update(mid);
        return mid;
    }
    bool check(ll x,ll y)
    {
        return A*x+B*y<C;
    }
    int pre(int x)
    {
        int tmp=0;
        tmp+=check(t[x].mn[0],t[x].mn[1]);
        tmp+=check(t[x].mx[0],t[x].mn[1]);
        tmp+=check(t[x].mn[0],t[x].mx[1]);
        tmp+=check(t[x].mx[0],t[x].mx[1]);
        return tmp;
    }
    void get_ans(int x)
    {
        if(check(t[x][0],t[x][1])) ans+=t[x].v;
        int dl=0,dr=0;
        if(ls) dl=pre(ls);if(rs) dr=pre(rs); 
        if(dl==4) ans+=t[ls].sum;
        else if(dl)get_ans(ls);
        if(dr==4) ans+=t[rs].sum;
        else if(dr) get_ans(rs);
    }
}kd;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) 
        p[i][0]=read(),p[i][1]=read(),p[i].v=read();
    root=kd.build(1,n,0);
    while(m--)
    {
        A=read();B=read();C=read();
        ans=0;kd.get_ans(root);
        printf("%lld\n",ans);
    }
}```