「BZOJ2850」巧克力王国

2015年5月2日6,6700

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力
都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。
对于每一块巧克力，我们设x和y为其牛奶和可可的含量。
由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数a和
b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x和y
的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有
甜味程度大于等于c的巧克力他都无法接受。
每块巧克力都有一个美味值h。
现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。

Input

第一行两个正整数n和m，分别表示巧克力个数和询问个数。

接下来n行，每行三个整数x,y,h，含义如题目所示。

再接下来m行，每行三个整数a,b,c，含义如题目所示。

Output

输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

Sample Input

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

Sample Output

5
0
4

HINT

对于100% 的数据，1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

题解

据说复杂度是每次询问期望√n

如果会KDtree的话看一眼代码应该就懂了

#include<cmath>
#include<cstdio>
#include<complex>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define inf 1000000000
#define mod 1000000007
#define sqr(x) x*x
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll A,B,C,ans;
int F,n,m,rt;
struct P{
	int d[2],mx[2],mn[2],v,l,r;
	ll sum;
	int& operator[](int x){
		return d[x];
	}
	friend bool operator<(P a,P b){
		return a[F]<b[F];
	}
}p[50005];
bool check(int x,int y)
{
	return A*x+B*y<C;
}
int cal(P x)
{
	int tmp=0;
	tmp+=check(x.mn[0],x.mn[1]);
	tmp+=check(x.mx[0],x.mn[1]);
	tmp+=check(x.mn[0],x.mx[1]);
	tmp+=check(x.mx[0],x.mx[1]);
	return tmp;
}
struct kd{
	P t[50005];
	void update(int k){
		int l=t[k].l,r=t[k].r;
		for(int i=0;i<2;i++)
		{
			t[k].mn[i]=t[k].mx[i]=t[k][i];
			if(l)t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);
			if(r)t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);
			if(l)t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
			if(r)t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
		}
		t[k].sum=t[k].v+t[l].sum+t[r].sum;
	}
	int build(int l,int r,int now){
		F=now;int mid=(l+r)>>1;
		nth_element(p+l,p+mid,p+r+1);
		t[mid]=p[mid];
		if(l<mid)t[mid].l=build(l,mid-1,now^1);
		if(r>mid)t[mid].r=build(mid+1,r,now^1);
		update(mid);
		return mid;
	}
	void query(int k){
		int l=t[k].l,r=t[k].r;
		if(check(t[k][0],t[k][1]))ans+=t[k].v;
		int tl=0,tr=0;
		if(l)tl=cal(t[l]);
		if(r)tr=cal(t[r]);
		if(tl==4)ans+=t[l].sum;
		else if(tl)query(l);
		if(tr==4)ans+=t[r].sum;
		else if(tr)query(r);
	}
}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();
	rt=kd.build(1,n,0);
	while(m--)
	{
		A=read(),B=read(),C=read();
		ans=0;
		kd.query(rt);
		printf("%lld\n",ans);
	}
	return 0;
}

#include<cmath>

#include<cstdio>

#include<complex>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000007

#define sqr(x) x*x

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll A,B,C,ans;

int F,n,m,rt;

struct P{

int d[2],mx[2],mn[2],v,l,r;

ll sum;

int& operator[](int x){

return d[x];

}

friend bool operator<(P a,P b){

return a[F]<b[F];

}

}p[50005];

bool check(int x,int y)

{

return A*x+B*y<C;

}

int cal(P x)

{

int tmp=0;

tmp+=check(x.mn[0],x.mn[1]);

tmp+=check(x.mx[0],x.mn[1]);

tmp+=check(x.mn[0],x.mx[1]);

tmp+=check(x.mx[0],x.mx[1]);

return tmp;

}

struct kd{

P t[50005];

void update(int k){

int l=t[k].l,r=t[k].r;

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

{

t[k].mn[i]=t[k].mx[i]=t[k][i];

if(l)t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);

if(r)t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);

if(l)t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);

if(r)t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);

}

t[k].sum=t[k].v+t[l].sum+t[r].sum;

}

int build(int l,int r,int now){

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

nth_element(p+l,p+mid,p+r+1);

t[mid]=p[mid];

if(l<mid)t[mid].l=build(l,mid-1,now^1);

if(r>mid)t[mid].r=build(mid+1,r,now^1);

update(mid);

return mid;

}

void query(int k){

int l=t[k].l,r=t[k].r;

if(check(t[k][0],t[k][1]))ans+=t[k].v;

int tl=0,tr=0;

if(l)tl=cal(t[l]);

if(r)tr=cal(t[r]);

if(tl==4)ans+=t[l].sum;

else if(tl)query(l);

if(tr==4)ans+=t[r].sum;

else if(tr)query(r);

}

}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();

rt=kd.build(1,n,0);

while(m--)

{

A=read(),B=read(),C=read();

ans=0;

kd.query(rt);

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

}

return 0;

}

« 「BZOJ1941」[SDOI2010] Hide and Seek 「BZOJ4066」简单题 »

分类目录

计数器 9863256
OI 课件=>

hzwer.com _ Home | http://hzwer.com