自动搬运

查看原文

来自洛谷，原作者为

	lzqy_ 生而绚烂，璀璨如花。

搬运于2025-08-24 22:28:41，当前版本为作者最后更新于2021-12-24 21:52:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑更简洁的 $\text{cdq}$ 做法。

约定：第 $i$ 个矩形左下角为 $(xl_i,yl_i)$，右上角为 $(xr_i,yr_i)$，所有坐标都已离散化。

如果 第 $i$ 个矩形可以覆盖第 $j$ 个矩形，那么必须满足：

• $i>j$

• $xl_i\le xr_j,xr_i\ge xl_j$（横向有交点）

• $yl_i\le yr_j,yr_i\ge yl_j$（竖向有交点）

首先将矩形按照出现的顺序降序排列，解决完第一个条件。

考虑满足 $xl_i\le xr_j$。将 $[l,mid]$ 按照 $xl$ 排序，$[mid+1,r]$ 按照 $xr$ 排序，然后将满足 $xl_i\le xr_j$ 条件的矩形存入线段树中（具体存法后文讲），这样在线段树中的矩形都随时满足 $xl_i\le xr_j$。

关键在于如何将矩形存储到线段树中来满足剩下三个条件。

将线段树看做纵坐标的值域，那么存储第 $i$ 个矩形就一定是对区间 $[yl_i,yr_i]$ 进行操作，且操作的值一定和 $xr_i$ 有关。

看到剩下的条件 $xr_i\ge xl_j$，发现 $xr_i$ 越大越好，于是存储矩形到线段树中的操作就很明了了，即 $[yl_i,yr_i]$ 更新最大值 $xr_i$。

设 $f_j$ 表示第 $j$ 个矩形是否被覆盖，线段树区间最大值为 $g_{[l,r]}$，那么就有：

所以执行一遍 $\text{cdq}$ 就全部搞定了。

关于线段树清空

在多设一个区间是否清空的懒标记，每次懒标记下传的时候，先下穿清空的懒标记，再下传正常的懒标记。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200010;
const int N=(maxn<<2);
inline int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
	return x;
}
struct node{
	int id,xl,yl,xr,yr;
}a[maxn];
int data[N],lz[N],LZ[N];
//data为区间最值,lz为正常懒标记,LZ为清空懒标记
int X[N],Y[N];
int n,m;
bool f[maxn];
bool cmp1(node a,node b){
	return a.xl<b.xl;
}
bool cmp2(node a,node b){
	return a.xr<b.xr;
}
bool cmp3(node a,node b){
	return a.id<b.id;
}
bool cmp4(node a,node b){
	return a.id>b.id;
}
void pushdown(int i){
	if(~LZ[i]){
	//先下传清空懒标记(可以思考下传递顺序的问题)
		lz[i<<1]=lz[i<<1|1]=0;
		data[i<<1]=data[i<<1|1]=0;
		LZ[i<<1]=LZ[i<<1|1]=0;
		LZ[i]=-1;
	} 
	lz[i<<1]=max(lz[i<<1],lz[i]);
	lz[i<<1|1]=max(lz[i<<1|1],lz[i]);
	data[i<<1]=max(data[i<<1],lz[i]);
	data[i<<1|1]=max(data[i<<1|1],lz[i]);
	lz[i]=0;
}
void add(int i,int l,int r,int L,int R,int x){
	if(l>R||r<L) return ;
	if(l>=L&&r<=R){
		data[i]=max(data[i],x);
		lz[i]=max(lz[i],x);
		return ;
	}
	pushdown(i);
	int mid=l+r>>1;
	add(i<<1,l,mid,L,R,x);
	add(i<<1|1,mid+1,r,L,R,x);
	data[i]=max(data[i<<1],data[i<<1|1]);
}
int Query(int i,int l,int r,int L,int R){
	if(l>R||r<L) return 0;
	if(l>=L&&r<=R) return data[i];
	pushdown(i);
	int mid=l+r>>1;
	return max(Query(i<<1,l,mid,L,R),Query(i<<1|1,mid+1,r,L,R));
}
void cdq(int l,int r){
	if(r-l<1) return ;
	int mid=l+r>>1,ii=l,x;
	cdq(l,mid),cdq(mid+1,r);
	sort(a+l,a+1+mid,cmp1);
	sort(a+mid+1,a+r+1,cmp2);
	//注意[l,mid][mid+1,r]排序方法不同
	for(int j=mid+1;j<=r;j++){//cdq常规操作
		while(ii<=mid&&a[ii].xl<=a[j].xr) 
			add(1,1,m,a[ii].yl,a[ii].yr,a[ii].xr),ii++;
		f[a[j].id]|=(Query(1,1,m,a[j].yl,a[j].yr)>=a[j].xl);
		//更新fj
	}
	data[1]=lz[1]=LZ[1]=0,pushdown(1);
	//将整个区间打上清空懒标记
	//不要忘记下传一层 
}
map<int,int>Hx,Hy;
int main(){
	n=read(),memset(LZ,-1,sizeof(LZ));
	int x,y,u,v,cntx=0,cnty=0,Cntx=0,Cnty=0;
	for(int i=1;i<=n;i++){
		a[i].id=i,x=read()+1,y=read()+1,u=read(),v=read();
		a[i].xl=x,a[i].yl=y,a[i].xr=x+u-1,a[i].yr=y+v-1;
		X[++cntx]=a[i].xl,X[++cntx]=a[i].xr;
		Y[++cnty]=a[i].yl,Y[++cnty]=a[i].yr;
	}
	sort(X+1,X+1+cntx),sort(Y+1,Y+1+cnty);
	Hx[X[1]]=++Cntx,Hy[Y[1]]=++Cnty;
	for(int i=2;i<=cntx;i++){
		if(X[i]!=X[i-1]) Hx[X[i]]=++Cntx;
		if(Y[i]!=Y[i-1]) Hy[Y[i]]=++Cnty;
	}
	for(int i=1;i<=n;i++){
	//离散化(其实xl,xr是不用离散化的)
		a[i].xl=Hx[a[i].xl],a[i].xr=Hx[a[i].xr];
		a[i].yl=Hy[a[i].yl],a[i].yr=Hy[a[i].yr];
	} 
	sort(a+1,a+1+n,cmp4),m=Cnty,cdq(1,n);
	for(int i=1;i<=n;i++) 
		printf("%s\n",f[i]?"NE":"DA");
	return 0;
}

祝 $\text{AC}$。