Rectangle Shrinking

· · 题解

用的是很直接的一个思路，但是模拟略复杂。

首先题目给出的矩形可以分为三类：只在第一行的，只在第二行的和横跨两行的。我们考虑以下几种情况的处理：

  1. 两个只在第一行的矩形重叠。任选一个修改边界使得两个矩形刚好相邻，面积不变。比如把范围在 [l,r] 和 [l',r'](l<l'<r<r') 的两个矩形改成两个范围在 [l,r] 和 [r+1,r'] 的矩形。

  2. 一行的矩形在横跨两行的矩形内部，直接删除一行的矩形。

  3. 一行的矩形的一个端点在横跨两行的矩形内部，那么修改这个一行矩形的在横跨两行的矩形的内部的边界使它与横跨两行的矩形相邻，如一个横跨两行的 [l,r] 与一个一行的 [l',r'](l<l'<r<r') 可修改为一个两行的 [l,r] 与一个一行的 [r+1,r']。

  4. 若横跨两行的矩形的范围包含在了只在一行的矩形的范围内，那么直接把这个横跨两行的矩形修改为只在另一行的矩形。

通过以上操作，并不改变矩形整体的面积，并且可以消除所有的重叠部分。具体操作见代码注释（可能模拟用的不是最方便的写法）。

#include<bits/stdc++.h>
using namespace std;
int t,n,u,d,l,r,cnta,cntb,cntc,cntea,cnteb,la,lb,lc,rc,squ;
struct T{
    int l,r,id;
    bool operator<(T a){
        return l==a.l?r<a.r:l<a.l;
    }
}a[200005],b[200005],c[200005],Exa[200005],exb[200005];
//a,b,c表示一开始读入后以及后续化简过程中留存的矩形，a表示只在第一行。 
//b表示只在第二行，c表示横跨两行。
//Exa与exb表示由原本是横跨两行的矩形转化而来的一行矩形。 
struct P{
    int u,l,d,r;
}ans[200005];
//用来处理情况1 
void simply(T* a,int &n){
    if(n==0)return;
    int l=0,r=1;
    while(r<n){
        while(r<n&&a[r].r<=a[l].r)r++;
        if(r==n)break;
        if(a[r].l<=a[l].r)a[r].l=a[l].r+1;
        l++;
        a[l]=a[r];
        r++;
    }
    n=l+1;
}
//用来处理情况2+3
void more_simply(T* a,int &n){
    if(n==0)return;
    lc=0;
    for(int i=0;i<n;i++){
        while(lc<cntc&&c[lc].r<a[i].l)lc++;
        if(lc==cntc)break;
        rc=lc;
        if(c[lc].l<=a[i].l)a[i].l=c[lc].r+1;
        while(rc<cntc&&c[rc].r<a[i].r)rc++;
        if(rc==cntc)break;
        if(c[rc].l<=a[i].r)a[i].r=c[rc].l-1;
    }
    int l=r=0;
    while(r<n){
        while(r<n&&a[r].l>a[r].r)r++;
        if(r==n)break;
        a[l]=a[r];
        l++;
        r++;
    }
    n=l;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        cnta=cntb=cntc=cntea=cnteb=squ=0;
        for(int i=0;i<=n;i++)a[i]=b[i]=c[i]=Exa[i]=exb[i]={0,0,0};
        for(int i=0;i<=n;i++)ans[i]={0,0,0,0};
        for(int i=0;i<n;i++){
            cin>>u>>l>>d>>r;
            if(u!=d)c[cntc++]={l,r,i};
            else if(u==1)a[cnta++]={l,r,i};
            else b[cntb++]={l,r,i};
        }
        sort(a,a+cnta);
        sort(b,b+cntb);
        sort(c,c+cntc);
        //排序后，后续操作都可以在线性时间复杂度内完成。 
        simply(a,cnta);
        simply(b,cntb);
        simply(c,cntc);
        more_simply(a,cnta);
        more_simply(b,cntb);
        la=lb=0;
        //处理情况4
        //枚举每一个横跨两行的矩形。
        //在上述两次化简后，最多只有一个只在第一行的矩形和一个只在第二行的矩形
        //可能与这个横跨两行的矩形重叠
        //并且如果重叠，那么一行矩形的范围必定包含两行矩形的范围。 
        for(int i=0;i<cntc;i++){
            while(la<cnta&&a[la].r<c[i].r)la++;
            while(lb<cntb&&b[lb].r<c[i].r)lb++; 
            //两行的一行矩形均与两行矩形重叠，直接删除两行矩形。 
            if(la<cnta&&lb<cntb&&a[la].l<=c[i].l&&b[lb].l<=c[i].l)c[i].l=c[i].r=0;
            //第一行的矩形与两行矩形重叠，将两行矩形转化为第二行的矩形 
            else if(la<cnta&&a[la].l<=c[i].l){
                exb[cnteb++]=c[i];
                c[i].l=c[i].r=0;
            //同上 
            }else if(lb<cntb&&b[lb].l<=c[i].l){
                Exa[cntea++]=c[i];
                c[i].l=c[i].r=0;
            }
        }
        //将所有的答案整合起来,顺便计算面积。
        //整合过程中不会访问被删去的矩形，所以ans中被删去的矩形对应的就是ans的初始值{0,0,0,0}; 
        for(int i=0;i<cnta;i++)ans[a[i].id]={1,a[i].l,1,a[i].r},squ+=a[i].r-a[i].l+1;
        for(int i=0;i<cntb;i++)ans[b[i].id]={2,b[i].l,2,b[i].r},squ+=b[i].r-b[i].l+1;
        for(int i=0;i<cntc;i++)if(c[i].l)ans[c[i].id]={1,c[i].l,2,c[i].r},squ+=2*(c[i].r-c[i].l+1);
        for(int i=0;i<cntea;i++)ans[Exa[i].id]={1,Exa[i].l,1,Exa[i].r},squ+=Exa[i].r-Exa[i].l+1;
        for(int i=0;i<cnteb;i++)ans[exb[i].id]={2,exb[i].l,2,exb[i].r},squ+=exb[i].r-exb[i].l+1;
        cout<<squ<<endl;
        for(int i=0;i<n;i++)printf("%d %d %d %d\n",ans[i].u,ans[i].l,ans[i].d,ans[i].r);
    }
}