自动搬运

查看原文

来自洛谷，原作者为

	andychen_2012 **

搬运于2025-08-24 23:10:09，当前版本为作者最后更新于2025-02-27 09:50:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考虑你的矩形 $S$ 的左端为 $L$，下端为 $D$，则右端为 $L+W$，上端为 $D+H$。类似的小矩形的四边坐标记作 $l_i,d_i,r_i,u_i$。

那么覆盖则须满足

$$L< \min r_i\\ D < \min d_i\\ L+W> \max l_i\\ D+H> \max u_i $$

我们将 $W,H$ 各减去 $1$，然后挪到右边去，同时考虑将 $L,D$ 变为整数坐标，则有

$$\max(l_i-W) \le L < \min(r_i+1)\\ \max(u_i-H) \le D < \min(d_i+1) $$

我们对 $L$ 这一维扫描线，然后将每一个加入或删除的矩形的上下端在线段树上维护，求最大前缀和即可。

代码如下：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0;
    int f=0,ch=0;
    while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?-x:x;
}
inline void write(ll x,char end='\n'){
    if(x==0){
        putchar('0');
        putchar(end);
        return;
    }
    if(x<0) putchar('-'),x=-x;
    int ch[40]={0},cnt=0;
    while(x){
        ch[cnt++]=(int)(x%10);
        x/=10;
    }
    while(cnt--) putchar(ch[cnt]+48);
    putchar(end);
}
const int N=1e5+5;
const int L=5e4+1;
int w,h;
int n;
struct mat{int l,d,r,u;}rec[N];
inline bool cmp(mat x,mat y){return x.r<y.r;}
vector<int> e[L+5];
int sum[N<<2],mxlsum[N<<2];
inline void pushup(int u){
	sum[u]=sum[u<<1]+sum[u<<1|1];
	mxlsum[u]=max(mxlsum[u<<1],sum[u<<1]+mxlsum[u<<1|1]);
}
inline void add(int u,int l,int r,int p,int v){
	if(l==r){
		sum[u]+=v;
		mxlsum[u]=max(sum[u],0);
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) add(u<<1,l,mid,p,v);
	else add(u<<1|1,mid+1,r,p,v);
	pushup(u);
}
inline void modify(int id,int v){
	add(1,1,L,max(rec[id].d,1),v);
	add(1,1,L,rec[id].u+1,-v);
}
int main(){
	w=read(),h=read();
	w--,h--;
	n=read();
	for(int i=1;i<=n;++i) rec[i]={read(),read()-h,read(),read()};
	for(int i=1;i<=n;++i){
		e[max(rec[i].l-w,0)].emplace_back(i);
		e[rec[i].r+1].emplace_back(-i);
	}
	int ans=0;
	for(int i=0;i<=L;++i){
		for(auto id:e[i]){
			if(id<0) modify(-id,-1);
			else modify(id,1);
		}
		ans=max(ans,mxlsum[1]);
	}
	write(ans);
    return 0;
}