题解：P11774 [COTS 2013] 矩形覆盖 / BAKTERIJE

· · 题解

考虑你的矩形 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;
}