自动搬运

查看原文

来自洛谷，原作者为

	yuzhechuan **

搬运于2025-08-24 22:03:41，当前版本为作者最后更新于2020-01-18 10:59:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

放一篇（可能）比较正常的cdq题解

题解：

题意显然是一个四维偏序，然而三只log的复杂度也显然是不优秀的

注意到题目只是让我们判定某个矩形能否被其他某一个矩形包括，而不是有几对关系，因此本题可以通过某些方法简化掉一层限制

考虑若矩形$j$要对矩形$i$产生贡献，即$j$包含$i$，需要满足$x_{j2}>x_{i2}$，$y_{j2}>y_{i2}$，$x_{j1}<x_{i1}$，$y_{j1}<y_{i1}$

假设我们此时已经用排序+分治干掉前两维了，$j$此时一定会排在$i$的前面，可以想象一下$i$的右上角已经被所有在区间$[l,p]$中的矩形的右上角包住了（p是合并时的左指针，能保证其中一层限制），现在只需要判定这部分的矩形的左下角能否包住$i$的左下角就好了

由于这是连贯且起始点是定值的区间，我们对他们记一个前缀min，看看对于某个点的左半边，有没有还比他低的点，这些点就是在它的左下角的了，在满足包住右上角的同时也能包住左下角，于是就可以判定矩形$i$能被另外某个矩形包住了

前缀min是树状数组的一个经典应用，可以log解决

最后统计一下有几个矩形能被包住就是答案

另外还有一个小细节，为了优化大坐标带来的复杂度冗余，我们可以先对横纵坐标离散化一下

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}


#define dc divide_and_conquer
#define xn XN
#define yn YN

const int N=2e5+5;
int ans,xn,yn,numx[N<<1],numy[N<<1],tr[N<<1],n;

struct dc{
	int x,y,xx,yy,ans;
	inline bool operator < (const dc &nt) const{ //先按右上角的x排
		return xx>nt.xx;
	}
}a[N],b[N];

#define lowbit(x) (x&(-x))

void clear(int x){ //重新赋回无穷大
	while(x<=xn){
		tr[x]=0x3f3f3f3f;
		x+=lowbit(x);
	}
}

void up(int x,int v){ //修改
	while(x<=xn){
		tr[x]=min(tr[x],v);
		x+=lowbit(x);
	}
}

int que(int x){ //查询
	int res=0x3f3f3f3f;
	while(x){
		res=min(res,tr[x]);
		x-=lowbit(x);
	}
	return res;
}

void cdq(int l,int r){
	if(l==r) return ;
	int mid=l+r>>1;
	cdq(l,mid);cdq(mid+1,r);
	int p=l,q=mid+1,i=l-1;
	while(p<=mid&&q<=r){
		if(a[p].yy>a[q].yy){ //满足右上角能包住
			up(a[p].x,a[p].y); //维护下前缀最小
			b[++i]=a[p++];
		}
		else{
			if(que(a[q].x)<a[q].y) a[q].ans=1; //若它的前面还有比他低的，就是被包住了
			b[++i]=a[q++];
		}
	}
	while(q<=r){
		if(que(a[q].x)<a[q].y) a[q].ans=1;
		b[++i]=a[q++];
	}
	for(int i=l;i<p;i++) clear(a[i].x); //复原树状数组
	while(p<=mid) b[++i]=a[p++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}

signed main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i].x);numx[++xn]=a[i].x;
		read(a[i].y);numy[++yn]=a[i].y;
		read(a[i].xx);numx[++xn]=a[i].xx;
		read(a[i].yy);numy[++yn]=a[i].yy;
	}
	memset(tr,0x3f,sizeof tr); //初始赋无穷大
	sort(numx+1,numx+1+xn);
	sort(numy+1,numy+1+yn);
	for(int i=1;i<=n;i++){
		a[i].x=lower_bound(numx+1,numx+1+xn,a[i].x)-numx; //离散坐标
		a[i].y=lower_bound(numy+1,numy+1+yn,a[i].y)-numy;
		a[i].xx=lower_bound(numx+1,numx+1+xn,a[i].xx)-numx;
		a[i].yy=lower_bound(numy+1,numy+1+yn,a[i].yy)-numy;
	}
	sort(a+1,a+1+n);
	cdq(1,n);
	for(int i=1;i<=n;i++) ans+=a[i].ans; //统计答案
	write(ans);
}