NOIP 模拟 $92; m 翻转游戏$

题解 (by;zjvarphi)

让求至少 (n-1) 个矩形共同覆盖的面积，可以先枚举强制哪个矩形没有覆盖，直接求剩下矩形的交。

求矩形的交时可以直接压一个前缀矩形的交，后缀矩形的交。

记得因为强制当前矩形不选，所以要把当前矩形也覆盖的面积减掉。

Code

#include<bits/stdc++.h>
#define ri signed
#define pd(i) ++i
#define bq(i) --i
#define func(x) std::function<x>
namespace IO{
    char buf[1<<21],*p1=buf,*p2=buf;
    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
    #define debug1(x) std::cerr << #x"=" << x << ' '
    #define debug2(x) std::cerr << #x"=" << x << std::endl
    #define Debug(x) assert(x)
    struct nanfeng_stream{
        template<typename T>inline nanfeng_stream &operator>>(T &x) {
            bool f=false;x=0;char ch=gc();
            while(!isdigit(ch)) f|=ch=='-',ch=gc();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
            return x=f?-x:x,*this;
        }
    }cin;
}
using IO::cin;
namespace nanfeng{
    #define FI FILE *IN
    #define FO FILE *OUT
    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
    using ll=long long;
    static const int N=3e5+7;
    int T,p,q,n;
    ll ans;
    struct node{int x1,y1,x2,y2;}pnt[N],f[N],tmp;
    auto merge=[](node n1,node n2) {
        if (n1.x1==-1||n2.x1==-1) return (node){-1,0,0,0};
        if (n1.x1>=n2.x2||n1.x2<=n2.x1) return (node){-1,0,0,0};
        if (n1.y1>=n2.y2||n1.y2<=n2.y1) return (node){-1,0,0,0};
        // debug1(n1.y1),debug2(n2.y1);
        return (node){cmax(n1.x1,n2.x1),cmax(n1.y1,n2.y1),cmin(n1.x2,n2.x2),cmin(n1.y2,n2.y2)};
    };
    inline int main() {
        FI=freopen("carpet.in","r",stdin);
        FO=freopen("carpet.out","w",stdout);
        cin >> T;
        for (ri z(1);z<=T;pd(z)) {
            cin >> p >> q >> n;
            for (ri i(1);i<=n;pd(i))
                cin >> pnt[i].x1 >>pnt[i].y1 >> pnt[i].x2 >> pnt[i].y2;
            f[n+1]=tmp={0,0,p,q};
            for (ri i(n);i;bq(i)) f[i]=merge(f[i+1],pnt[i]);
            ans=0;
            for (ri i(1);i<=n;pd(i)) {
                node nw=merge(tmp,f[i+1]),ch=merge(nw,pnt[i]);
                if (nw.x1!=-1) ans+=1ll*(nw.y2-nw.y1)*(nw.x2-nw.x1);
                if (ch.x1!=-1) ans-=1ll*(ch.y2-ch.y1)*(ch.x2-ch.x1);
                tmp=merge(tmp,pnt[i]);
                if (tmp.x1==-1) break;
            }
            if (f[1].x1!=-1) ans+=1ll*(f[1].y2-f[1].y1)*(f[1].x2-f[1].x1);
            printf("%lld
",ans);
        }
        return 0;
    }
}
int main() {return nanfeng::main();}