半平面数点求卡常
查看原帖
半平面数点求卡常
508032
int08楼主2024/7/3 08:30

第一遍交的 90,后面尽显颓势,越卡越慢。

快读加过了,好像没啥用)

#include<bits/stdc++.h>
using namespace std;
struct choco{
	int x,y,c[5];
};
#define BN 123
#define N 200803
#define pii pair<int,int> 
#define ll long long
vector<pii> p[2*N];
int x[N],y[N],c[N][5];
vector<choco> m[BN][BN];
int n,q,i,j,k;
ll a[5][BN][BN],s[5][BN][BN],all[5];
const int bl=200,sd=10000,bn=102;
int l[BN],r[BN];
#define xb(x) (((x)+sd)/bl+1)
int t[2*N],cn;
void change(int x,int v)
{
	for(;x<=cn;x+=x&-x) t[x]+=v;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x) ans+=t[x];
	return ans;
}
int ls[2*N];
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0); 
	cin>>n>>q;
	for(i=1;i<=n;i++)
		cin>>x[i]>>y[i],ls[++cn]=x[i],ls[++cn]=y[i];
	sort(ls+1,ls+cn+1),cn=unique(ls+1,ls+cn+1)-ls-1;
	for(i=1;i<=n;i++)
	{
		int rx=lower_bound(ls+1,ls+cn+1,x[i])-ls,ry=lower_bound(ls+1,ls+cn+1,y[i])-ls;
		p[rx].push_back({ry,i});
	}
	for(i=1;i<=cn;i++)
	{
		for(auto x:p[i]) c[x.second][1]=ask(x.first-1),all[1]+=c[x.second][1];
		for(auto x:p[i]) change(x.first,1);all[0]+=p[i].size();
		for(auto x:p[i]) c[x.second][2]=all[0]-ask(x.first-1)-1,all[2]+=c[x.second][2];
	}
	all[0]=0;
	memset(t,0,sizeof(t));
	for(i=cn;i>=1;i--)
	{
		for(auto x:p[i]) c[x.second][4]=all[0]-ask(x.first),all[4]+=c[x.second][4];
		for(auto x:p[i]) change(x.first,1);all[0]+=p[i].size();
		for(auto x:p[i]) c[x.second][3]=ask(x.first)-1,all[3]+=c[x.second][3];
	}
	
	for(i=1;i<=n;i++)
	{
		c[i][0]=1;
		int xl=xb(x[i]),yl=xb(y[i]);
		choco res;
		res.x=x[i],res.y=y[i];
		for(j=0;j<5;j++) a[j][xl][yl]+=c[i][j],res.c[j]=c[i][j];
		m[xl][yl].push_back(res);
	}
	for(i=1;i<=bn;i++) l[i]=(((i)-1)*bl-sd),r[i]=((i)*bl-sd-1);
	for(i=1;i<=bn;i++)
		for(j=1;j<=bn;j++)
			for(k=0;k<5;k++)
				s[k][i][j]=s[k][i][j-1]+a[k][i][j];
	while(q--)
	{
		ll a,b,c,ans=0,ans0=0;
		cin>>a>>b>>c;c*=-1;
		if(b==0)
		{
			int line=(c+((a<0)?1:0))/a,tp=(a<0)?1:4;
			for(i=1;i<=bn;i++)
			{
				if(r[i]<line) {ans+=s[tp][i][bn];continue;}
				if(l[i]>line) break;
				for(j=1;j<=bn;j++)
				for(auto p:m[i][j]) if(a>0&&a*p.x<=c||a<0&&a*p.x>c) ans+=p.c[tp];
				break;
			}
			if(a>0) ans=all[tp]-ans;
			cout<<ans<<'\n';
			continue;
		}
		int tp;
		if(a*b>=0) tp=b>0?4:1;
		else tp=b>0?2:3;
		for(i=1;i<=bn;i++)
		{
			ll y1=xb((c-a*l[i]+((b<0)?1:0))/b),y2=xb((c-a*r[i]+((b<0)?1:0))/b);
			if(y1>y2) swap(y2,y1);
			if(y1>bn)
			{
				ans+=s[tp][i][bn],ans0+=s[0][i][bn];
				continue;
			}
			if(y2<1) continue;
			y1=max(y1,1ll);y2=min(y2,(ll)(bn));
			ans+=s[tp][i][y1-1];
			ans0+=s[0][i][y1-1];
			for(j=y1;j<=y2;j++)
			for(auto p:m[i][j]) if(b<0&&a*p.x+b*p.y>c||b>0&&a*p.x+b*p.y<=c) ans+=p.c[tp],ans0+=p.c[0];
		}
		if(b>0) ans=all[tp]-ans,ans0=all[0]-ans0;
		if(a*b<0) ans=(ans0-1)*ans0/2-ans;
		cout<<ans<<'\n';
	}
	return 0;
}
2024/7/3 08:30
加载中...