题解：AT_abc432_d [ABC432D] Suddenly, A Tempest

· · 题解

首先注意到 n 很小，只有 14，说明指数级的复杂度都是可以通过的，那么重点就是如何模拟了。

考虑一次操作的实质：

那么我们仅需维护矩形以及以上操作就行。一个矩形可以使用左下角+右上角的方式存储。

可以发现经过以上操作之后的矩形是两两不交的。

然后统计连通块。我们可以暴力两两枚举，判断是否连通。实际上就是四个方向，判断是否相邻，然后判断线段是否有交，这个可以看代码。

如果发现有两个矩形相邻，那么这两个矩形就在同一个连通块中，连通块的合并可以使用并查集来维护。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct poi{
    ll x,y;
};
struct rect{
    poi d,u;
};
vector<rect> vec;
vector<rect> nw;
ll area(rect r){
    return (r.u.x-r.d.x+1)*(r.u.y-r.d.y+1);
}
rect addx(rect r,ll d){
    r.d.x+=d;
    r.u.x+=d;
    return r;
}
rect addy(rect r,ll d){
    r.d.y+=d;
    r.u.y+=d;
    return r;
}
void splitx(ll a,ll b,rect r){
    if(r.u.x<a){
        nw.push_back(addy(r,-b));
        return;
    }
    if(r.d.x>=a){
        nw.push_back(addy(r,b));
        return;
    }
    nw.push_back(addy((rect){r.d,(poi){a-1,r.u.y}},-b));
    nw.push_back(addy((rect){(poi){a,r.d.y},r.u},b));
}
void splity(ll a,ll b,rect r){
    if(r.u.y<a){
        nw.push_back(addx(r,-b));
        return;
    }
    if(r.d.y>=a){
        nw.push_back(addx(r,b));
        return;
    }
    nw.push_back(addx((rect){r.d,(poi){r.u.x,a-1}},-b));
    nw.push_back(addx((rect){(poi){r.d.x,a},r.u},b));
}
bool intersect(ll l,ll r,ll x,ll y){
    return !(r<x || y<l);
}
bool islian(rect a,rect b){
    return (
    ((a.u.y==b.d.y-1 || a.d.y-1==b.u.y) && intersect(a.d.x,a.u.x,b.d.x,b.u.x)) ||
    (a.u.x==b.d.x-1 || a.d.x-1==b.u.x) && intersect(a.d.y,a.u.y,b.d.y,b.u.y));
}
ll fa[(1<<15)],siz[(1<<15)],len;
void init(ll x){
    len=x;
    for(int i=0;i<len;i++){
        fa[i]=i;
        siz[i]=area(vec[i]); 
    }
}
ll Find(ll x){
    if(fa[x]==x)return x;
    else return fa[x]=Find(fa[x]);
}
void merg(ll x,ll y){
    ll fx=Find(x),fy=Find(y);
    if(fx==fy)return;
    fa[fx]=fy;
    siz[fy]+=siz[fx];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,x,y;
    cin>>n>>x>>y; 
    vec.push_back((rect){{0,0},{x-1,y-1}});
    for(int i=1;i<=n;i++){
        char ch;
        ll A,B;
        cin>>ch>>A>>B;
        nw.clear();
        if(ch=='X'){
            for(auto i:vec){
                splitx(A,B,i);
            }
        }else{
            for(auto i:vec){
                splity(A,B,i);
            }
        }
        vec=nw;
    }
    init(vec.size());
    for(int i=0;i<vec.size();i++){
        for(int j=i+1;j<vec.size();j++){
            if(islian(vec[i],vec[j])){
                merg(i,j);
            }
        }
    }
    vector<ll> ans;
    for(int i=0;i<vec.size();i++){
        if(Find(i)!=i)continue;
        ans.push_back(siz[i]);
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<" ";
    }
    return 0;
}