LINK：P4475 巧克力王国
又复习了一遍KDT 这道题不需要 重构 所以没套替罪羊树.(神EI 说KDT在这道题上复杂度是假的 我不太懂
其实最重要的除了写法之外 还有一个比较重要的trick?
就是 查最远最近距离的时候的剪枝 其实我也有点忘了 大概乱写一下 只要正确 适时进行modify即可.
这道题 可以利用KDT 来优化暴力 因为 对于前面的限制可以看成二维平面上的点.
然后 每次查询查询一个矩形到当前点的最近最远距离 来进行剪枝即可.
注意开 long long
code
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 1000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define vep(p,n,i) for(RE int i=p;i<n;++i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 13331ll
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define EPS 1e-5
#define sq sqrt
#define S second
#define F first
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define v(x) t[x].v
#define mod 998244353
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
RE int x=0,f=1;RE char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
inline ll Read()
{
RE ll x=0,f=1;RE char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
const int MAXN=50010,K=2;
int n,m,D,rt;
ll xx,yy,c,ans;
struct wy
{
int l,r;ll sum,v;
int d[K];
int mx[K],mn[K];
}t[MAXN];
int q[MAXN];
inline int cmp(int a,int b){return t[a].d[D]<t[b].d[D];}
inline void pushup(int x)
{
if(!l(x)&&!r(x))return;
sum(x)+=sum(l(x))+sum(r(x));
vep(0,K,i)
{
if(l(x))t[x].mx[i]=max(t[x].mx[i],t[l(x)].mx[i]),t[x].mn[i]=min(t[x].mn[i],t[l(x)].mn[i]);
if(r(x))t[x].mx[i]=max(t[x].mx[i],t[r(x)].mx[i]),t[x].mn[i]=min(t[x].mn[i],t[r(x)].mn[i]);
}
}
inline int build(int l,int r,int k)
{
if(l>r)return 0;
int mid=(l+r)>>1;D=k;
nth_element(q+l,q+mid,q+r+1,cmp);
int x=q[mid];sum(x)=v(x);
vep(0,K,i)t[x].mx[i]=t[x].d[i],t[x].mn[i]=t[x].d[i];
l(x)=build(l,mid-1,(k+1)%K);
r(x)=build(mid+1,r,(k+1)%K);
pushup(x);return x;
}
inline int check(int x)
{
if(t[x].d[0]*xx+t[x].d[1]*yy>=c)return 0;
return 1;
}
inline void ask(int x)
{
ll maxx,minn;
if(xx>0)maxx=t[x].mx[0]*xx,minn=t[x].mn[0]*xx;else maxx=t[x].mn[0]*xx,minn=t[x].mx[0]*xx;
if(yy>0)maxx+=t[x].mx[1]*yy,minn+=t[x].mn[1]*yy;else maxx+=t[x].mn[1]*yy,minn+=t[x].mx[1]*yy;
if(maxx<c){ans+=sum(x);return;}
if(minn>=c)return;
if(check(x))ans+=v(x);
if(l(x))ask(l(x));
if(r(x))ask(r(x));
}
int main()
{
//freopen("1.in","r",stdin);
get(n);get(m);
rep(1,n,i)t[i].d[0]=read(),t[i].d[1]=read(),get(v(i)),q[i]=i;
rt=build(1,n,0);
rep(1,m,i)
{
get(xx),get(yy),get(c);
ans=0;ask(rt);putl(ans);
}
return 0;
}