bzoj 2850 巧克力王国——KDtree

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2850

改一下估价即可。判断子树能否整个取或者是否整个不能取，时间好像就能行了？

因为有负数，所以判一下四个边界。注意这个区域本身还占了一个点。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=5e4+;

int n,m,rt,tot,fx;

ll A,B,C;

struct Dt{

    ll x[],y[],p[],h,ph;

}a[N];

bool cmp(Dt u,Dt v){return u.p[fx]<v.p[fx];}

struct KD{

    int c[N][];Dt s[N];

    void add(int cr,Dt k)

    {

        for(int i=;i<=;i++) s[cr].x[i]=s[cr].y[i]=s[cr].p[i]=k.p[i];

        s[cr].h=s[cr].ph=k.h;

    }

    void pshp(int cr)

    {

        int ls=c[cr][],rs=c[cr][];

        for(int i=;i<=;i++)

        {

            if(ls)  s[cr].x[i]=min(s[cr].x[i],s[ls].x[i]),

                    s[cr].y[i]=max(s[cr].y[i],s[ls].y[i]);

            if(rs)  s[cr].x[i]=min(s[cr].x[i],s[rs].x[i]),

                    s[cr].y[i]=max(s[cr].y[i],s[rs].y[i]);

        }

        s[cr].h=(ls?s[ls].h:)+(rs?s[rs].h:)+s[cr].ph;

    }

    void build(int &cr,int l,int r,bool now)

    {

        int mid=l+r>>;  fx=now;  nth_element(a+l,a+mid,a+r+,cmp);

        cr=++tot;  add(cr,a[mid]);

        if(l<mid) build(c[cr][],l,mid-,!now);

        if(mid<r) build(c[cr][],mid+,r,!now);

        pshp(cr);

//        printf("cr=%d(x:%lld~%lld y:%lld~%lld h=%lld)\n",cr,s[cr].x[0],

//            s[cr].y[0],s[cr].x[1],s[cr].y[1],s[cr].h);

    }

    int check(int cr)

    {

        int ret=;

        ret+=(A*s[cr].x[]+B*s[cr].x[]<C);

        ret+=(A*s[cr].x[]+B*s[cr].y[]<C);

        ret+=(A*s[cr].y[]+B*s[cr].x[]<C);

        ret+=(A*s[cr].y[]+B*s[cr].y[]<C);

        return ret;

    }

    ll query(int cr)

    {

        ll ret=(A*s[cr].p[]+B*s[cr].p[]<C?s[cr].ph:);

        int ls=c[cr][],rs=c[cr][];

        int dl=(ls?check(ls):),dr=(rs?check(rs):);

//        printf("cr=%d(x:%lld~%lld y:%lld~%lld h=%lld) dl=%d dr=%d\n"

//            ,cr,s[cr].x[0],s[cr].y[0],s[cr].x[1],s[cr].y[1],s[cr].h,dl,dr);

        if(dl==) ret+=s[ls].h;  else if(dl) ret+=query(ls);

        if(dr==) ret+=s[rs].h;  else if(dr) ret+=query(rs);

        return ret;

    }

}kd;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        scanf("%lld%lld%lld",&a[i].p[],&a[i].p[],&a[i].h);

    kd.build(rt,,n,);

    for(int i=;i<=m;i++)

    {

        scanf("%lld%lld%lld",&A,&B,&C);

        printf("%lld\n",kd.query(rt));

    }

    return ;

}