题目内容

Solution

对于每个询问可以拆分成4个前缀矩形的求和，容易发现，前缀矩形的求和相当于是求一个二维偏序，可以用树状数组或cdq分治在nlogn的复杂度内完成。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar('0'+x%10);
}//Make sure that the left won't make a difference to the right
//If it is true,there is no need to unique 
const int N=1e5+100;
int n,m,ans[N];
struct node{
	int x,y,z,p,sum,id,tag;
	bool operator<(const node& g)const
	{
		if(x^g.x) return x<g.x;
		if(y^g.y) return y<g.y;
		return z<g.z;
	}
}a[N*5],tmp[N*5];
int cnt;
void cdq(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int sum=0,pos=l;
	for(int i=mid+1;i<=r;++i)
	{
		while(pos<=mid&&a[pos].y<=a[i].y) sum+=a[pos].p,pos++;
		a[i].sum+=sum;
	}
	int p=l,q=mid+1;
	for(int i=l;i<=r;++i)
	  if(p>mid) tmp[i]=a[q++];
	  else if(q>r) tmp[i]=a[p++];
	  else tmp[i]=a[a[p].y<a[q].y?p++:q++];
	for(int i=l;i<=r;++i) a[i]=tmp[i];
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
    	int x=read(),y=read(),p=read();
    	a[i]={x,y,0,p};
	}
	cnt=n;
	for(int i=1;i<=m;++i)
	{
		int x[3],y[3];
		x[1]=read(),y[1]=read();
		x[2]=read(),y[2]=read();
		a[++cnt]={x[2],y[2],1,0,0,i,1};
		a[++cnt]={x[2],y[1]-1,1,0,0,i,-1};
		a[++cnt]={x[1]-1,y[2],1,0,0,i,-1};
		a[++cnt]={x[1]-1,y[1]-1,1,0,0,i,1};
	}
	sort(a+1,a+cnt+1);
	cdq(1,cnt);
	for(int i=1;i<=cnt;++i)
	if(a[i].z)
	ans[a[i].id]+=a[i].sum*a[i].tag;
	for(int i=1;i<=m;++i)
	{
		write(ans[i]);puts("");
	}
	return 0;
}