就是bit求二维偏序啊

悬赏永久关注,谢谢!

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+10;
int n,Q;
struct Nd{
	int x,y;
	int id,val,sign,op;
}a[N];
vector<int> nums;//离散化数组 
void pb(int x){
	nums.push_back(x);
}
int tr[N];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int c){
	for(int i=x;i<=nums.size();i+=lowbit(i)) tr[i]+=c;
}
int query(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
	return res;
}
int find(int x){
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int ans[N];
bool cmp(Nd x,Nd y){
	return x.x==y.x?x.y<y.y:x.x<y.x;
}//一定要双关键字 
int q;
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].val);
		pb(a[i].x);pb(a[i].y);
	}
	int x1,y1,x2,y2;
	for(int i=1;i<=q;i++){
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		pb(x1-1),pb(y1-1),pb(x2),pb(y2);
		a[++n]={x1-1,y1-1,i,0,1,1};
		a[++n]={x1-1,y2,i,0,-1,1};
		a[++n]={x2,y1-1,i,0,-1,1};
		a[++n]={x2,y2,i,0,1,1};
	}
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	for(int i=1;i<=n;i++){
		a[i].x=find(a[i].x)+1;
		a[i].y=find(a[i].y)+1;
		//BIT要下标从1开始，所以用vec离散化需要+1 
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		if(!a[i].op) add(a[i].y,a[i].val);
		else ans[a[i].id]+=a[i].sign*query(a[i].y);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;   
}