第一遍交的 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;
}