長方形の結合の観察

長方形の結合を続けて行うことを考えます. \((h_1,w_1)\) から始めて, \((h_2,w_2)\) を結合し, 続けて \((h_3,w_3)\) を結合したとします. このとき, \((h_2,w_2)\) が縦/横向きに結合できたならば \((h_3,w_3)\) が縦/横向きに結合できる, という条件を考えます.

例えば, \(h_2=h_3\) が成り立つとき, \((h_2,w_2)\) が横向きに結合できたならば \((h_3,w_3)\) が横向きに結合できる, が成り立ちます. 同様に, \(w_2=w_3\) が成り立つとき, \((h_2,w_2)\) が縦向きに結合できたならば \((h_3,w_3)\) が縦向きに結合できる, が成り立ちます.

向きが異なる結合を考えましょう. このときは, 必ずしも \((h_2,w_2),(h_3,w_3)\) のみから条件が成り立つかどうかがわかりません. しかし, \((h_2,w_2)\) が結合する長方形の面積が一意に定まります.

例えば, \((h_2,w_2)\) が縦向きに結合できたとし, \((h_3,w_3)\) が横向きに結合できるのは, \((h_1,w_1)\) の面積が \((h_3-h_2)w_2\) であるとき, またそのときに限ります.

グラフへの対応と数え上げ

条件を満たす \((l,r)\) の組の個数を数え上げましょう. \(l\) を固定したとき, \((l,r)\) が条件を満たすかどうかは \(r\) に対して単調性があります. そこで \(l\) を固定します.

\(l\) を固定したことで, 連続する \(2\) つの長方形の結合の向きについて, 先方が結合できるなら後方が結合できるという条件の真偽が分かります. そこで, その情報を \(2\times N\) 頂点のグラフに表しましょう.

\(i=1,2,\dots ,N\) について, 頂点 \(i\) は \((H_i,W_i)\) が縦向きに結合することを表し, 頂点 \(N+i\) は \((H_i,W_i)\) が横向きに結合することを表すこととします.

\(i=2,3,\dots ,N\) について, 以下を行います.

• \((H_{i-1},W_{i-1})\) が縦向きに結合できたならば \((H_i,W_i)\) が縦向きに結合できる, という条件が成り立つとき頂点 \(i-1,i\) の間に辺を張る.
• \((H_{i-1},W_{i-1})\) が縦向きに結合できたならば \((H_i,W_i)\) が横向きに結合できる, という条件が成り立つとき頂点 \(i-1,N+i\) の間に辺を張る.
• \((H_{i-1},W_{i-1})\) が横向きに結合できたならば \((H_i,W_i)\) が縦向きに結合できる, という条件が成り立つとき頂点 \(N+i-1,i\) の間に辺を張る.
• \((H_{i-1},W_{i-1})\) が横向きに結合できたならば \((H_i,W_i)\) が横向きに結合できる, という条件が成り立つとき頂点 \(N+i-1,N+i\) の間に辺を張る.

便宜上, \((H_l,W_l)\) は横向きにも縦向きにも結合できたとします. このとき, 頂点 \(l,N+l\) のいずれかと頂点 \(r,N+r\) のいずれかが連結であることが \((l,r)\) が条件を満たすことと同値です.

向きの異なる結合に対応する辺は, 高々 \(1\) つの \(l\) に対してのみ張られることになります. 一方, 向きの同じ結合に対応する辺は, 張られるならどの \(l\) に対しても張られることになります.

グラフの辺を \(2\times 2\) 行列で表したものをセグメントツリーに乗せます. 条件を満たす最大の \(r\) をセグメントツリー上の二分探索で, グラフの更新をセグメントツリーの更新で行えば, すべての \(l\) で合わせて \(\mathrm{O}(N\log N)\) 時間の計算量で処理することができます.