巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。对于每一块巧克力，我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少
1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。
这个题不告诉我 我不会写kdtree的 （所以我就不会写了）
维护一下子树权值和
当一个节点内包含的所有情况都满足条件时 ans+=子树权值和
再顺着有可能的点遍历 就结束了
查询复杂度期望O(√n)
觉得挺玄学
然而想一想觉得好像也确实卡不掉
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<map> #include<set> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(ll x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=50010,inf=0X7f7f7f7f; int root; bool cur; struct P { int d[2],mn[2],mx[2],ls,rs;ll sum,val; inline int& operator [](int x){return d[x];} friend bool operator < (const P &x,const P &y){return x.d[cur]<y.d[cur];} }p[N]; struct kdtree { P tr[N];ll ans,a,b,c; inline void pushup(int k) { register int i; for(i=0;i<2;++i) { tr[k].mn[i]=tr[k].mx[i]=tr[k][i]; if(tr[k].ls)tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].ls].mx[i]),tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].ls].mn[i]); if(tr[k].rs)tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].rs].mx[i]),tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].rs].mn[i]); } tr[k].sum+=tr[tr[k].ls].sum+tr[tr[k].rs].sum; } int build(int l,int r,bool now) { cur=now;int mid=l+r>>1; nth_element(p+l,p+mid,p+r+1); tr[mid]=p[mid]; if(mid>l)tr[mid].ls=build(l,mid-1,now^1); if(mid<r)tr[mid].rs=build(mid+1,r,now^1); pushup(mid);return mid; } inline ll getsweet(int x,int y) {return 1ll*x*a+1ll*y*b;} inline int check(int k) { register int tmp=0; if(getsweet(tr[k].mn[0],tr[k].mn[1])<c)tmp++; if(getsweet(tr[k].mn[0],tr[k].mx[1])<c)tmp++; if(getsweet(tr[k].mx[0],tr[k].mn[1])<c)tmp++; if(getsweet(tr[k].mx[0],tr[k].mx[1])<c)tmp++; return tmp; } void query_limsum(int k) { if(getsweet(tr[k][0],tr[k][1])<c)ans+=tr[k].val; int tmp; if(tr[k].ls) { tmp=check(tr[k].ls); if(!(tmp^4))ans+=tr[tr[k].ls].sum; else if(tmp)query_limsum(tr[k].ls); } if(tr[k].rs) { tmp=check(tr[k].rs); if(!(tmp^4))ans+=tr[tr[k].rs].sum; else if(tmp)query_limsum(tr[k].rs); } } inline ll query(int x,int y,int z) { a=x,b=y,c=z;ans=0;query_limsum(root); return ans; } }kdtree; int main() { int n=read(),Q=read(); register int i,j,k; for(i=1;i<=n;++i) {p[i][0]=read();p[i][1]=read();p[i].sum=p[i].val=read();} root=kdtree.build(1,n,0); while(Q--) { i=read();j=read();k=read(); print(kdtree.query(i,j,k));puts(""); } return 0; } /* 3 3 1 2 5 3 1 4 2 2 1 2 1 6 1 3 5 1 3 7 5 0 4 */
