cdq分治太美妙了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,id,qi,lsh[2000010],ln;
struct N{
	int op,x,y,v,id;
}a[1000010];
bool cmp(N a,N b){
	return a.x<b.x;
}
ll ans[100010];
int lowbit(int x){
	return x&(-x);
}
struct BIT{
	ll tr[2000010];
	void add(int x,ll v){
		for(int i=x;i<=ln;i+=lowbit(i))tr[i]+=v;
	}
	ll find(int x){
		ll ans=0;
		for(int i=x;i;i-=lowbit(i))ans+=tr[i];
		return ans;
	}
}tr;
void solve(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(a+l,a+mid+1,cmp);
	sort(a+mid+1,a+r+1,cmp);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&a[j].x<=a[i].x){
			if(a[j].op==0)tr.add(a[j].y,a[j].v);
			j++;
		}
		if(a[i].op==1)ans[a[i].id]+=a[i].v*tr.find(a[i].y);
	}
	for(int i=l;i<j;i++)if(a[i].op==0)tr.add(a[i].y,-a[i].v);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1,x,y,v;i<=n;i++){
		cin>>x>>y>>v;
		a[++id]={0,x,y,v,0};
		lsh[++ln]=x;lsh[++ln]=y;
	}
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		if(op==0){
			int x,y,v;
			cin>>x>>y>>v;
			a[++id]={0,x,y,v,0};
			lsh[++ln]=x;lsh[++ln]=y;
		}
		else{
			int x1,y1,x2,y2;
			cin>>x1>>y1>>x2>>y2;
			x1--;x2--;y1--;y2--;
			qi++;
			a[++id]={1,x2,y2,1,qi};
			a[++id]={1,x1,y2,-1,qi};
			a[++id]={1,x2,y1,-1,qi};
			a[++id]={1,x1,y1,1,qi};
			lsh[++ln]=x1;lsh[++ln]=y1;
			lsh[++ln]=x2;lsh[++ln]=y2;
		}
	}
	sort(lsh+1,lsh+1+ln);
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=id;i++){
		a[i].x=lower_bound(lsh+1,lsh+1+ln,a[i].x)-lsh;
		a[i].y=lower_bound(lsh+1,lsh+1+ln,a[i].y)-lsh;
	}
	solve(1,id);
	for(int i=1;i<=qi;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}