⚠️ 多少発展的な内容を含みます。E くらいまで着手できる人用です。ある種の「思考停止解法」を欲している人向けです。

「黒く塗られたマスが連続する区間」の個数を数えるための半群を考えます。 問題設定から、次の情報を持っていればよさそうです。

• 着目している範囲の左端の色
• 着目している範囲の右端の色
• 着目している範囲に存在する「黒く塗られたマスが連続する区間」の個数

たとえば、着目している区間が □■□□■■□■□□■■ の場合、(白, 黒, 4) になります。また、□ と ■ に相当する元は、それぞれ (白, 白, 0) と (黒, 黒, 1) です。

積も自然に考えることができます。内側にくる部分の色（左オペランドにおける右端の色と、右オペランドにおける左端の色）が両方とも黒だった場合、「黒く塗られたマスが連続する区間」の個数は、元々の個数の和より 1 小さくなります。それ以外の場合は元々の個数の和になります。

形式的な元を単位元として適当に作ることでモノイドを構成することができるため、あとはセグ木を用いて、任意の区間における「黒く塗られたマスが連続する区間」を求めることができます。

note: たとえば、(無色, 無色, 0) という元を考えて、それとの積は他方の元を返すことにすればよいです。単位元の性質から (黒, 黒, 1) × (無色, 無色, 0) × (黒, 黒, 1) = (黒, 黒, 1) × (黒, 黒, 1) = (黒, 黒, 1) になるべきで、(黒, 無色, 1) × (黒, 黒, 1) = (黒, 黒, 2) になっては困るので、元々の半群の積をそのまま流用すると破綻します。

コード：提出 #67026433