CDQ分治 WAon#4#7求调
查看原帖
CDQ分治 WAon#4#7求调
626005
zhr2021楼主2024/1/25 19:44
#include<bits/stdc++.h>
#define L long long
using namespace std;
const L N=1e6+10;
L n,m,cnt;
struct data{
	L x,y,val,typ,t;
}a[N],b[N];
bool cmp(data x,data y){
	if(x.x!=y.x) return x.x<y.x;
	if(x.x!=y.x) return x.y<y.y;
	return x.typ<y.typ;
}
bool cmp2(data x,data y){
	return x.t<y.t;
}
void CDQ(L l,L r){
	if(l>=r) return;
	L mid=(l+r)>>1;
	CDQ(l,mid);CDQ(mid+1,r);
	L i=l,j=mid+1,p=l,cnt=0;
	while(j<=r){
		while(a[i].y<=a[j].y&&i<=mid){
			if(a[i].typ==1) cnt+=a[i].val;
			b[p++]=a[i++];
		}
		if(a[j].typ==2) a[j].val+=cnt;
		b[p++]=a[j++];
	}
	while(i<=mid) b[p++]=a[i++];
	while(j<=r) b[p++]=a[j++];
	for(L i=l;i<=r;i++){
		a[i]=b[i];
	}
}
int main(){
	cin>>n>>m;
	for(L i=1;i<=n;i++){
		L x,y;
		cin>>x>>y;
		x++,y++;
		a[++cnt]={x,y,1,1,cnt};
	}
	for(L i=1;i<=m;i++){
		L xa,ya,xb,yb;
		cin>>xa>>ya>>xb>>yb;
		xb++,yb++;
		a[++cnt]={xa,ya,0,2,cnt};
		a[++cnt]={xb,yb,0,2,cnt};
		a[++cnt]={xa,yb,0,2,cnt};
		a[++cnt]={xb,ya,0,2,cnt};
	}
	sort(a+1,a+cnt+1,cmp);
	CDQ(1,cnt);
	sort(a+1,a+cnt+1,cmp2);
	for(L i=1;i<=cnt;i++){
		if(a[i].typ==2){
			cout<<a[i].val+a[i+1].val-a[i+2].val-a[i+3].val<<"\n";
			i+=3;
		}
	}
	return 0;
}
2024/1/25 19:44
加载中...