[SHOI2007]园丁的烦恼

[SHOI2007]园丁的烦恼

BZOJ
luogu
二维偏序入门题
询问拆成四个点
按x排序,离散化y树状数组查
细节的话:x,y都相同优先修改
空间5倍

#define lb(i) (i&-i)
#include<bits/stdc++.h>
using namespace std;
const int _=2500005;
int re(){
	int x=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*w;
}
int n,m,cnt,tot,ly;
int f[_],t[_],ans[_];
struct node{int x,y,op,id;}p[_];
bool cmp(node a,node b){
	if(a.x==b.x){
		if(a.y==b.y)return a.op==0;
		return a.y<b.y;
	}
	return a.x<b.x;
}
void add(int i){while(i<=ly)t[i]++,i+=lb(i);}
int sum(int i){int s=0;while(i)s+=t[i],i-=lb(i);return s;}
int main(){
	tot=cnt=n=re(),m=re();
	for(int i=1;i<=n;i++){
		int x=re();f[i]=re();
		p[i]=(node){x,f[i]};
	}
	for(int i=1;i<=m;i++){
		int a=re(),b=re(),c=re(),d=re();
		f[++cnt]=b-1;f[++cnt]=d;
		p[++tot]=(node){a-1,b-1,1,i};
		p[++tot]=(node){a-1,d,-1,i};
		p[++tot]=(node){c,b-1,-1,i};
		p[++tot]=(node){c,d,1,i};
	}
	sort(f+1,f+cnt+1);
	ly=unique(f+1,f+cnt+1)-f-1;
	for(int i=1;i<=tot;i++)
		p[i].y=lower_bound(f+1,f+ly+1,p[i].y)-f;
	sort(p+1,p+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		if(!p[i].op)add(p[i].y);
		else ans[p[i].id]+=p[i].op*sum(p[i].y);
	}
	for(int i=1;i<=m;i++)printf("%d
",ans[i]);
	return 0;
}