巧克力王国 bzoj-2850
题目大意：给出n块巧克力，每块巧克力都有自己的两个参数x和y和本身的价值val，询问：m个人，每个人有两个系数和一个限度a,b,和c。求所有ax+by<=c的巧克力价值和。
注释：$1\le n,n\le 5\cdot 10^4$。
想法：我们将巧克力的两个参数分别当作它的横纵坐标，然后对于每一次询问就可以转化成查询给定直线下的点的点权和。
对于这个问题，我们可以建立KD-Tree解决。
估价函数就是看这个矩形是不是都选或者都不选，否则的话，就遍历这个矩形。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
using namespace std;
typedef long long ll;
int d,root;
struct Node
{
ll c[2],p[2],maxn[2],minn[2],v,sum;
}a[N];
inline bool cmp(const Node &x,const Node &y)
{
return x.p[d]==y.p[d]?x.p[d^1]<y.p[d^1]:x.p[d]<y.p[d];
}
inline void pushup(int k,int s)
{
a[k].maxn[0]=max(a[k].maxn[0],a[s].maxn[0]);
a[k].minn[0]=min(a[k].minn[0],a[s].minn[0]);
a[k].maxn[1]=max(a[k].maxn[1],a[s].maxn[1]);
a[k].minn[1]=min(a[k].minn[1],a[s].minn[1]);
a[k].sum+=a[s].sum;
}
int build(int l,int r,int now)
{
int mid=(l+r)>>1;
d=now; nth_element(a+l,a+mid,a+r+1,cmp);
a[mid].maxn[0]=a[mid].minn[0]=a[mid].p[0];
a[mid].maxn[1]=a[mid].minn[1]=a[mid].p[1];
a[mid].sum=a[mid].v;
if(l<mid) a[mid].c[0]=build(l,mid-1,now^1),pushup(mid,a[mid].c[0]);
if(mid<r) a[mid].c[1]=build(mid+1,r,now^1),pushup(mid,a[mid].c[1]);
return mid;
}
int getdis(int k,ll x,ll y,ll z)
{
if(x >= 0 && y >= 0)
{
if(x*a[k].maxn[0]+y*a[k].maxn[1]<z) return 1;
if(x*a[k].minn[0]+y*a[k].minn[1]>=z) return -1;
}
else if(x < 0 && y >= 0)
{
if(x*a[k].minn[0]+y*a[k].maxn[1]<z) return 1;
if(x*a[k].maxn[0]+y*a[k].minn[1]>=z) return -1;
}
else if(x >= 0 && y < 0)
{
if(x*a[k].maxn[0]+y*a[k].minn[1]<z) return 1;
if(x*a[k].minn[0]+y*a[k].maxn[1]>=z) return -1;
}
else
{
if(x*a[k].minn[0]+y*a[k].minn[1]<z) return 1;
if(x*a[k].maxn[0]+y*a[k].maxn[1]>=z) return -1;
}
return 0;
}
ll query(int k,ll x,ll y,ll z)
{
int opt=getdis(k,x,y,z);
if(opt==1) return a[k].sum;
if(opt==-1) return 0;
ll ans=0;
if(x*a[k].p[0]+y*a[k].p[1]<z) ans+=a[k].v;
if(a[k].c[0]) ans+=query(a[k].c[0],x,y,z);
if(a[k].c[1]) ans+=query(a[k].c[1],x,y,z);
return ans;
}
int main()
{
int n,m;
ll x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].p[0],&a[i].p[1],&a[i].v);
root=build(1,n,0);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&x,&y,&z),printf("%lld\n",query(root,x,y,z));
return 0;
}
小结：这道题还挺裸的... ...