离散化+树状数组统计 

看到这题第一个反应二维树状数组 看数据范围 这画风不对啊……

考虑离线解决这个问题

首先离散化y轴坐标

我们发现可以把一个询问拆成4个询问 一个是从(0,0)到(cj,dj)一个从(0,0)到(aj-1,bj-1)一个从(0,0)到(aj-1,dj)一个从(0,0)到(cj,bj-1)，然后这个询问就可以用这几个相加减弄出来了。

将询问和树按横坐标排序后 从左往右扫一遍 遇到树就将其加入树状数组，遇到询问就查询一下，最后计算一下答案输出

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=4000000;
struct query{int x,y,y0,op,id;}q[N+10];
struct tree{int x,y;}t[N+10];
int s[N+10],ans[N+10],n,m,cnt=0,tmp=0;
bool cmp(query a,query b){return a.x==b.x?a.op<b.op:a.x<b.x;}
bool cmp2(query a,query b){return a.y<b.y;}
bool cmp3(query a,query b){return a.id<b.id;}
void add(int x,int d){for(;x<=tmp;x+=x&-x) s[x]+=d;}
int sum(int x){int ret=0;for(;x;x-=x&-x) ret+=s[x];return ret;}
void read(int &x){char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1935.in","r",stdin);freopen("1935.out","w",stdout);
	// scanf("%d%d",&n,&m);
	read(n),read(m);q[0].y=-65478;
	for(int i=1;i<=n;i++) read(q[i].x),read(q[i].y);
	for(int i=1;i<=m;i++) {
		int x1,y1,x2,y2;
		read(x1);read(y1);read(x2);read(y2);
		// scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		q[n+(++cnt)].x=x1-1;//q1;
		q[n+cnt].y=y1-1;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x1-1;//q2;
		q[n+cnt].y=y2;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x2;//q3;
		q[n+cnt].y=y1-1;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x2;//q4;
		q[n+cnt].y=y2;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;//ans[i]=q4-q2-q3+q1
	}
	sort(q+1,q+n+4*m+1,cmp2);
	for(int i=1;i<=n+4*m;i++) {if(q[i].y!=q[i-1].y) tmp++;q[i].y0=tmp;}
	sort(q+1,q+n+4*m+1,cmp);
	for(int i=1;i<=n+4*m;i++){
		if(!q[i].op) add(q[i].y0,1);
		else ans[q[i].id]=sum(q[i].y0);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[4*i]-ans[4*i-1]-ans[4*i-2]+ans[4*i-3]);
	return 0;
}