题解：AT_abc432_d [ABC432D] Suddenly, A Tempest

首先注意到

n

很小，只有

14

，说明指数级的复杂度都是可以通过的，那么重点就是如何模拟了。

考虑一次操作的实质：

切割一个矩形，支持横向和纵向切割。
将矩形平移 $B$ 个单位。支持横向和竖向平移。

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

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

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

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

CPP

#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;
}

题解：AT_abc432_d [ABC432D] Suddenly, A Tempest

文章操作

相关推荐

评论

题解：AT_abc432_d [ABC432D] Suddenly, A Tempest