CDQ分治
对于这道题，可以参考 P4390 [BOI2007]Mokia 摩基亚 的做法,可以通过 CDQ 分治离线操作高效处理出答案（我常数大,不能体现出 CDQ 分治的优秀)。
可以发现,操作 11 和操作 22 分好了界限,于是我们只需要统计答案，不用再使用树状数组维护。
对于 CDQ 分治,我们可以先看一道例题（逆序对）：
//这是很经典的二维偏序问题，满足下标和值的大小关系即可。
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);cdq(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(a[i]<=a[j])tmp[k++]=a[i++];
else ans+=mid-i+1,tmp[k++]=a[j++];
}
while(i<=mid)tmp[k++]=a[i++];
while(j<=r)tmp[k++]=a[j++];
for(int i=l;i<=r;i++)a[i]=tmp[i];
}很显然,本题也是一个二维偏序问题。对于询问 xx yy ,查询 \sum_{i=0}^x\sum_{j=0}^y val_{i,j}∑i=0x∑j=0yvali,j ，val_{i,j}vali,j 为点 (i,j)(i,j) 的值。
对于 ii 的贡献,我们只需要找到 x_i<x_j,y_i<y_jxi<xj,yi<yj 对于每个数对,答案加上 ii 位置的权值,具体实现和逆序对相似。
先按照 xx 排个序,在分治算法中找到 y_i<y_jyi<yj 的数对即可。
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);cdq(mid+1,r);
int i=l,j=mid+1,k=l,cnt=0;
while(j<=r&&i<=mid){
if(q[i].y<=q[j].y){
if(q[i].typ==1)cnt+=q[i].a;//对于i，yj>yi,且y点有值，那么加上
tmp[k++]=q[i++];
}else{
if(q[j].typ==2)q[j].a+=cnt;//如果q[j].y<q[i].y,那么j这个点的贡献加上之前累加的cnt，因为这里的i是上一次询问的i，没动过。
tmp[k++]=q[j++];
}
}
while(i<=mid){//再次统计一遍，以免漏掉
if(q[i].typ==1)cnt+=q[i].a;
tmp[k++]=q[i++];
}
while(j<=r){
if(q[j].typ==2)q[j].a+=cnt;
tmp[k++]=q[j++];
}
for(int i=l;i<=r;i++)q[i]=tmp[i];//归并排序
}最后按照询问的时间排序,运用差分知识统计一下矩阵和即可：
#include<cstdio>
#include<algorithm>
#define N 1919810
#define int long long
using namespace std;
int n,m,tot;
struct node{
int x,y,typ,a,t;
}q[N],tmp[N];
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
else if(a.y!=b.y)return a.y<b.y;
return a.typ<b.typ;
}
bool cmp2(node a,node b){return a.t<b.t;}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);cdq(mid+1,r);
int i=l,j=mid+1,k=l,cnt=0;
while(j<=r&&i<=mid){
if(q[i].y<=q[j].y){
if(q[i].typ==1)cnt+=q[i].a;
tmp[k++]=q[i++];
}else{
if(q[j].typ==2)q[j].a+=cnt;
tmp[k++]=q[j++];
}
}
while(i<=mid){
if(q[i].typ==1)cnt+=q[i].a;
tmp[k++]=q[i++];
}
while(j<=r){
if(q[j].typ==2)q[j].a+=cnt;
tmp[k++]=q[j++];
}
for(int i=l;i<=r;i++)q[i]=tmp[i];
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)q[++tot].typ=1,q[tot].t=tot,scanf("%lld%lld%lld",&q[tot].x,&q[tot].y,&q[tot].a);
for(int i=1;i<=m;i++){
int x,y,xx,yy;
scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
q[++tot].x=xx,q[tot].y=yy,q[tot].typ=2,q[tot].t=tot;
q[++tot].x=x-1,q[tot].y=yy,q[tot].typ=2,q[tot].t=tot;
q[++tot].x=xx,q[tot].y=y-1,q[tot].typ=2,q[tot].t=tot;
q[++tot].x=x-1,q[tot].y=y-1,q[tot].typ=2,q[tot].t=tot;
}
sort(q+1,q+tot+1,cmp);
cdq(1,tot);
sort(q+1,q+tot+1,cmp2);
for(int i=n+1;i<=tot;i++){
printf("%lld\n",q[i].a-q[i+1].a-q[i+2].a+q[i+3].a);
i+=3;
}
return 0;
}