bzoj 2850: 巧克力王国 K-D树

题目大意

题解

对于每个人,我们发现它能够接受的巧克力中

如果对参数分别讨论,那么一定是一个连续的区间

所以我们利用K-D划分维度,然后直接搜就好了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(ll &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline ll min(ll a,ll b,ll c){return min(a,min(b,c));}

inline ll max(ll a,ll b,ll c){return max(a,max(b,c));}

const int maxn = 50010;

const int dem = 2;

struct Node{

	ll pos[2],sum,val;

	ll minn[2],maxx[2];

	Node *ch[2];

	void update(){

		minn[0] = min(pos[0],ch[0]->minn[0],ch[1]->minn[0]);

		maxx[0] = max(pos[0],ch[0]->maxx[0],ch[1]->maxx[0]);

		minn[1] = min(pos[1],ch[0]->minn[1],ch[1]->minn[1]);

		maxx[1] = max(pos[1],ch[0]->maxx[1],ch[1]->maxx[1]);

		sum = val + ch[0]->sum + ch[1]->sum;

	}

}*null,*root;

Node T[maxn],aNoUseNode;

inline void init(){

	null = &aNoUseNode;null->ch[0] = null->ch[1] = null;

	null->sum = null->val = 0;

	null->minn[0] = 1LL<<60;null->maxx[0] = -(1LL<<60);

	null->minn[1] = 1LL<<60;null->maxx[1] = -(1LL<<60);

}

int split[maxn],now;

inline bool cmp(const Node &a,const Node &b){

	return a.pos[split[now]] < b.pos[split[now]];

}

Node *build(int l,int r,int s){

	if(l > r) return null;

	int mid = (l+r) >> 1;

	split[now = mid] = s % dem;

	nth_element(T+l,T+mid,T+r+1,cmp);

	Node *p = &T[mid];

	p->ch[0] = build(l,mid-1,s+1);

	p->ch[1] = build(mid+1,r,s+1);

	p->update();return p;

}

ll a,b,c;

inline bool judge1(Node *p){

	return (a*p->minn[0] + b*p->minn[1] < c)

	&& (a*p->minn[0] + b*p->maxx[1] < c)

	&& (a*p->maxx[0] + b*p->minn[1] < c)

	&& (a*p->maxx[0] + b*p->maxx[1] < c);

}

inline bool judge2(Node *p){

	return (a*p->minn[0] + b*p->minn[1] >= c)

	&& (a*p->minn[0] + b*p->maxx[1] >= c)

	&& (a*p->maxx[0] + b*p->minn[1] >= c)

	&& (a*p->maxx[0] + b*p->maxx[1] >= c);

}

ll query(Node *p){

	if(p == null) return 0;

	ll ret = 0;

	if(a*p->pos[0] + b*p->pos[1] < c) ret += p->val;

	if(judge1(p->ch[0])) ret += p->ch[0]->sum;

	else if(!judge2(p->ch[0])) ret += query(p->ch[0]);

	if(judge1(p->ch[1])) ret += p->ch[1]->sum;

	else if(!judge2(p->ch[1])) ret += query(p->ch[1]);

	return ret;

}

int main(){

	init();

	ll n,m;read(n);read(m);

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

		read(T[i].pos[0]);read(T[i].pos[1]);

		read(T[i].val);T[i].ch[0] = T[i].ch[1] = null;

		T[i].update();

	}

	root = build(1,n,1);

	while(m--){

		read(a);read(b);read(c);

		printf("%lld\n",query(root));

	}

	getchar();getchar();

	return 0;

}