問題概要
（原文参照）
準備
各セル $( x, y )$ の左下の角が平面上の座標 $( x, y )$ に位置するように座標系をとります．
ひとつの長方形を $4$ つの整数の組 $( x_1, x_2, y_1, y_2 )$ で表現することにし．平面上の点 $( x, y )$ は，$x \in [ x_1, x_2 )$ かつ $y \in [ y_1, y_2 )$ のとき，かつそのときに限りこの長方形に含まれるとします．言い換えれば，長方形を $x$ 軸，$y$ 軸にそれぞれ射影したときの半開区間をもつということです．更に記法として，長方形 $R = ( x_1, x_2, y_1, y_2 )$ に対して，タプルのそれぞれの要素を先頭から順に $R.x_1, R.x_2, R.y_1, R.y_2$ と書くことにします．また，プログラム上でバラバラにして扱うと見通しが悪くなるので
struct Rectangle
{
LL x1, x2, y1, y2;
};
という構造体にします*1．
解法
個人的に題意を読み取りづらかったので，まず大嵐（以降「操作」とします）について整理します．$C_i$ が X のときは直線 $x = A_i$ で平面をぶった切って，左側を下に $B_i$，右側を上に $B_i$ 平行移動します．（各セルから見ると「$( x, y + B_i )$ の色になる」ですが外から見ると負方向への平行移動であることに注意します．）同様に，$C_i$ が Y のときは直線 $y = A_i$ で平面をぶった切って，下側を左に $B_i$，上側を右に $B_i$ 並行移動します．
やることそのものは公式解説の通りなのですが，全体の方針からすると細かい，けれど実装する上で必須な部分が『$O( 1 )$ でできるので』で済まされてしまっていたりそもそも触れられてすらいなかったりするので，このあたりを中心に書きます．
さて，黒セルの情報を長方形の集合で表現して管理するわけですが，操作が行われたときに何が起きるかを整理します．長方形 $( x_1, x_2, y_1, y_2 )$ は，操作で平面をぶった切る直線がその proper な内部を通るか否かによって以下のように異なる影響を受けます：
- 直線が内部を通らないとき : 全体が平行移動し，ひとつの長方形のまま残る
- 直線が内部を通るとき : その直線を境に逆方向への平行移動が起こり，$2$ つの長方形になる
内部を通らないときの条件を整理すると，
- $C_i$ が
Xで，- $A_i \leq x_1$ のとき，下に並行移動
- $x_2 \leq A_i$ のとき，上に平行移動
- $C_i$ が
Yで，- $A_i \leq y_1$ のとき，左に並行移動
- $y_2 \leq A_i$ のとき，右に平行移動
となります．直線が内部を通る場合は，$C_i$ が X のときは長方形 $( x_1, x_2, y_1, y_2 )$ が $2$ つの長方形 $( x_1, A_i, y_1, y_2 ), ( A_i, x_2, y_1, y_2 )$ に分割され，前者を下に平行移動，後者を上に平行移動となります．同様に，$C_i$ が Y のときは長方形 $( x_1, x_2, y_1, y_2 )$ が $2$ つの長方形 $( x_1, x_2, y_1, A_i ), ( x_1, x_2, A_i, y_2 )$ に分割され，前者を下に平行移動，後者を上に平行移動となります．これで，最終的な黒セルの配置を計算するところまでできました．
連結成分を求めるには $2$ つの長方形の組合せ全てに渡ってその $2$ つの長方形が辺接触しているか否かを判定し，隣接していれば Disjoint Set Union で同じグループにマージするということをします．辺接触の判定は，水平な辺で接触する場合と垂直な辺で接触する場合に分けて考えます．しかしその前に，$2$ つの半開区間 $[ a, b ), [ c, d )$ が交叉する (i.e., $[ a, b ) \cap [ c, d ) \neq \emptyset$) 条件を確認します．図を描くなどすると確認できると思いますが，
\[
[ a, b ) \cap [ c, d ) \neq \emptyset \Leftrightarrow \max( a, c ) < \min( b, d )
\]
です．では本題の長方形の辺接触条件を考えます．長方形 $R, S$ に対して
，（今回の問題設定では）水平な辺で接するとは，
\[
[ R.x_1, R.x_2 ) \cap [ S.x_1, S.x_2 ) \neq \emptyset \land
\min( R.y_2, S.y_2 ) = \max( R.y_1, S.y_1 )
\]
を満たすことと同値です．自然言語で説明すると，
- それぞれの長方形を $x$ 軸に射影したものたちに共通部分がある
- 下にある長方形の上端と，上にある長方形の下端の座標が同じ
ということです．垂直な辺で接する場合は上記の縦横と $x, y$ を入れ替えた形になります．接触の判定ができたので，二重ループを回すなどしながら Disjoint Set Union を操作すれば連結成分を求められます．
連結成分に関連付けられた面積の集計にはいくつかやりようがあるかと思いますが，連結成分に値を関連付けて適切にマージできるタイプ*2を持っていると楽かもしれません（面積 $0$ になっているものを remove_if する必要があったりしますが）．
コード
class DisjointSetForest; // 中身省略 // DisjointSetForest( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) template < typename T > class DisjointSetForestAssociated : public DisjointSetForest // 中身省略 // DisjointSetForestAssociated( n, void( T&, T& ) ) // set( i, T ) // get( i ) struct Rectangle { LL x1, x2, y1, y2; Rectangle para_move( const int dx, const int dy ) const { return { x1 + dx, x2 + dx, y1 + dy, y2 + dy }; } }; bool adjacent( const Rectangle &p, const Rectangle &q ) { return max( p.x1, q.x1 ) < min( p.x2, q.x2 ) && min( p.y2, q.y2 ) == max( p.y1, q.y1 ) || max( p.y1, q.y1 ) < min( p.y2, q.y2 ) && min( p.x2, q.x2 ) == max( p.x1, q.x1 ); } VT< Rectangle > divide( const Rectangle &rec, const char C, const int A, const int B ) { const int dx = B * ( C != 'Y' ? 0 : rec.y2 <= A ? -1 : 1 ); const int dy = B * ( C != 'X' ? 0 : rec.x2 <= A ? -1 : 1 ) ; if ( C == 'X' && ( A <= rec.x1 || rec.x2 <= A ) || C == 'Y' && ( A <= rec.y1 || rec.y2 <= A ) ) { return { rec.para_move( dx, dy ) }; } else if ( C == 'X' ) { return { Rectangle{ rec.x1, A, rec.y1, rec.y2 }.para_move( dx, -dy ), Rectangle{ A, rec.x2, rec.y1, rec.y2 }.para_move( dx, dy ) }; } else { return { Rectangle{ rec.x1, rec.x2, rec.y1, A }.para_move( -dx, dy ), Rectangle{ rec.x1, rec.x2, A, rec.y2 }.para_move( dx, dy ) }; } } int main() { IN( int, N, X, Y ); VT< Rectangle > currents, nexts; currents.EB( 0, X, 0, Y ); REP( N ) { IN( char, C ); IN( int, A, B ); FOR( rect, currents ) { const auto res = divide( rect, C, A, B ); copy( ALL( res ), BI( nexts ) ); } swap( currents, nexts ); nexts.clear(); } const int M = SZ( currents ); DisjointSetForestAssociated< LL > dsf( M, []( LL &a, const LL &b ){ a += b; } ); for ( const auto &[ i, rec ] : views::enumerate( currents ) ) { const auto &[ x1, x2, y1, y2 ] = rec; dsf.set( i, ( x2 - x1 ) * ( y2 - y1 ) ); } REP( i, M ) { REP( j, i ) { if ( adjacent( currents[i], currents[j] ) ) { dsf.unite( i, j ); } } } VLL res( M ); REP( i, M ) { res[ dsf.find( i ) ] = dsf.get( i ); } res.erase( remove_if( ALL( res ), bind( equal_to< int >(), _1, 0 ) ), end( res ) ); sort( ALL( res ) ); cout << SZ( res ) << endl; cout << res << endl; return 0;
