以x和y作为坐标建立kdtree，然后维护某一棵子树内的美味值之和，如果同一颗子树的四个角的甜味都小于h，那么就可以直接累加进去。虽然这样的最坏时间复杂度仍然是$o(n^{2})$，但可以卡过去。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 50005 4 #define ll long long 5 int n,m,t,r; 6 ll x,y,z,ans; 7 struct ji{ 8 int a[2],s[2],mn[2],mx[2],k; 9 ll sum; 10 bool operator < (const ji &p)const{ 11 return a[t]<p.a[t]; 12 } 13 }a[N]; 14 bool pd(int *a){ 15 return x*a[0]+y*a[1]<z; 16 } 17 void up(int k){ 18 for(int i=0;i<2;i++)a[k].mn[i]=a[k].mx[i]=a[k].a[i]; 19 a[k].sum=a[k].k; 20 for(int i=0;i<2;i++) 21 if (a[k].s[i]){ 22 int s=a[k].s[i]; 23 a[k].sum+=a[s].sum; 24 for(int j=0;j<2;j++){ 25 a[k].mn[j]=min(a[k].mn[j],a[s].mn[j]); 26 a[k].mx[j]=max(a[k].mx[j],a[s].mx[j]); 27 } 28 } 29 } 30 int build(int l,int r,int p){ 31 int m=(l+r>>1); 32 t=p; 33 nth_element(a+l,a+m,a+r+1); 34 if (l<m)a[m].s[0]=build(l,m-1,p^1); 35 if (m<r)a[m].s[1]=build(m+1,r,p^1); 36 up(m); 37 return m; 38 } 39 void add(int &k,int p){ 40 t=p; 41 if (!k)k=n; 42 else add(a[k].s[a[k]<a[n]],p^1); 43 up(k); 44 } 45 int gj(int k){ 46 if (!k)return 0; 47 int ans=pd(a[k].mn)+pd(a[k].mx); 48 if (x*a[k].mn[0]+y*a[k].mx[1]<z)ans++; 49 if (x*a[k].mn[1]+y*a[k].mx[0]<z)ans++; 50 return ans; 51 } 52 void query(int k){ 53 if (!k)return; 54 if (pd(a[k].a))ans+=a[k].k; 55 for(int i=0;i<2;i++){ 56 int s=a[k].s[i],l=gj(s); 57 if (l==4)ans+=a[s].sum; 58 else query(s); 59 } 60 } 61 int main(){ 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].a[0],&a[i].a[1],&a[i].k); 64 r=build(1,n,0); 65 for(int i=1;i<=m;i++){ 66 scanf("%lld%lld%lld",&x,&y,&z); 67 ans=0; 68 query(r); 69 printf("%lld\n",ans); 70 } 71 }