p4475 巧克力王国

传送门

分析

我们多维护一个值，代表某个点子树中所有点的权值和

于是如果某个点它的min和max乘a(/b)的值小于范围则直接把整个子树都加进去

估价函数就是这个点的子树中的理论最小值

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define int long long

const int inf = 1e9;

inline int ra(){

    int x=,f=;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-;s=getchar();}

    while(isdigit(s))x=(x<<)+(x<<)+(s-''),s=getchar();

    return x*f;

}

struct kd {

    int d[],mx[],mn[],le,ri,id,sum,val;

};

kd t[],now;

int n,m,root,wh,Ans;

inline bool operator < (kd a,kd b){

    return a.d[wh]<b.d[wh];

}

inline void up(int rt){

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

      t[rt].mn[i]=min(t[rt].mn[i],min(t[t[rt].le].mn[i],t[t[rt].ri].mn[i]));

      t[rt].mx[i]=max(t[rt].mx[i],max(t[t[rt].le].mx[i],t[t[rt].ri].mx[i]));

    }

    t[rt].sum=t[t[rt].le].sum+t[t[rt].ri].sum+t[rt].val;

}

inline void build(int &x,int le,int ri,int wwh){

    wh=wwh;

    int mid=(le+ri)>>;

    x=mid;

    nth_element(t+le,t+x,t+ri+);

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

      t[x].mn[i]=t[x].mx[i]=t[x].d[i];

    if(le<x)build(t[x].le,le,mid-,wwh^);

    if(ri>x)build(t[x].ri,mid+,ri,wwh^);

    up(x);

}

inline int getd(kd a,kd b){

    if(!a.id)return inf;

    int res=;

    for(int i=;i<;++i)res+=a.d[i]*b.d[i];

    return res;

}

inline int calc(int x){

    if(!x)return inf;

    int res=;

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

      res+=min(t[x].mn[i]*now.d[i],t[x].mx[i]*now.d[i]);

    return res;

}

inline int getmax(int x){

    if(!x)return inf;

    int res=;

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

      res+=max(t[x].mn[i]*now.d[i],t[x].mx[i]*now.d[i]);

    return res;

}

inline void qurey(int x){

    if(!x)return;

    if(getmax(x)<now.val){

      Ans+=t[x].sum;

      return;

    }

    int dl=calc(t[x].le),dr=calc(t[x].ri),d=getd(t[x],now);

    if(d<now.val)Ans+=t[x].val;

    if(dl<now.val)qurey(t[x].le);

    if(dr<now.val)qurey(t[x].ri);

}

signed main(){

    int i,j,k;

    t[].mn[]=t[].mn[]=inf;

    t[].mx[]=t[].mx[]=-inf;

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

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

      t[i].d[]=ra(),t[i].d[]=ra(),t[i].val=ra();

      t[i].id=i;

    }

    build(root,,n,);

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

      Ans=;

      now.d[]=ra(),now.d[]=ra(),now.val=ra();

      qurey(root);

      printf("%lld\n",Ans);

    }

    return ;

}