直接离散化之后用树状数组扫一遍。
把每一个询问拆成四个就可以做了。
%Silvernebula 怒写KD-Tree
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i)
#define ll long long
#define mp make_pair
#define maxn 400005 void Finout()
{
freopen("task.in","r",stdin);
freopen("task.out","w",stdout);
} struct Query{
ll opt,x,y,id,p;
Query(){}
Query(ll _x,ll _y,ll _id,ll _opt)
{x=_x;y=_y;id=_id;opt=_opt;p=0;}
void print()
{printf("The Option is %lld (%lld,%lld) ID %lld p %lld\n",opt,x,y,id,p);}
bool operator < (const Query a) const{
if (x==a.x&&opt==a.opt) return y<a.y;
if (x==a.x) return abs(opt)<abs(a.opt);
return x<a.x;
}
}q[maxn<<2]; ll ans[maxn]; struct Bit_Tree{
ll a[maxn];
void add(ll x,ll f)
{
for(;x<maxn;x+=x&(-x))a[x]+=f;
}
ll gs(ll x)
{
ll ret=0;
for (;x;x-=x&(-x)) ret+=a[x];
return ret;
}
}Bt; ll n,m,tot;
ll lsx[maxn],lsy[maxn],topx,topy;
ll X1[maxn],Y1[maxn],X2[maxn],Y2[maxn]; int main()
{
scanf("%lld%lld",&n,&m);tot=n;
F(i,1,n)
{
scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].p);
lsx[i]=q[i].x;lsy[i]=q[i].y; q[i].opt=0;q[i].id=i;
}
topx=topy=n;
F(i,1,m)
{
scanf("%lld%lld%lld%lld",&X1[i],&Y1[i],&X2[i],&Y2[i]);
lsx[++topx]=X1[i];lsx[++topx]=X2[i];
lsy[++topy]=Y1[i];lsy[++topy]=Y2[i];
}
lsx[++topx]=-1e15; lsy[++topy]=-1e15;
lsx[++topx]=-1e14; lsy[++topy]=-1e14;
sort(lsx+1,lsx+topx+1); sort(lsy,lsy+topy+1);
F(i,1,n)
{
q[i].x=lower_bound(lsx+1,lsx+topx+1,q[i].x)-lsx;
q[i].y=lower_bound(lsy+1,lsy+topy+1,q[i].y)-lsy;
}
F(i,1,m)
{
X1[i]=lower_bound(lsx+1,lsx+topx+1,X1[i])-lsx;
X2[i]=lower_bound(lsx+1,lsx+topx+1,X2[i])-lsx;
Y1[i]=lower_bound(lsy+1,lsy+topy+1,Y1[i])-lsy;
Y2[i]=lower_bound(lsy+1,lsy+topy+1,Y2[i])-lsy;
q[++tot]=Query(X2[i],Y2[i],i,1); q[++tot]=Query(X1[i]-1,Y1[i]-1,i,1);
q[++tot]=Query(X2[i],Y1[i]-1,i,-1);q[++tot]=Query(X1[i]-1,Y2[i],i,-1);
}
sort(q+1,q+tot+1);
F(i,1,tot)
{
if (q[i].opt==0) Bt.add(q[i].y,q[i].p);
else
ans[q[i].id]+=q[i].opt*Bt.gs(q[i].y);
}
F(i,1,m) printf("%lld\n",ans[i]);
}