典型を使う前の手順のヒント

ヒント 1

シミュレーションをします。このとき、他のレンガで覆われてしまった面は考えなくてよいです。言い方を変えると、その時点で各部分で最も高い面のみを考えればよいです。

ヒント 2

新しく積むレンガの上面の高さは、(その範囲で最も高い面の高さ) $+1$ $(=h)$ です。その後、その範囲の高さは $h$ で置き換わります。

ヒント 3

各マスの最も高い面の高さを表す数列 $\{ A_n \}$ に対して次の操作ができればよいです。

$l,r$ が与えられて、 $A_l,A_{l+1}, \cdots ,A_r$ の最大値を求める

$l,r,h$ が与えられて、 $A_l,A_{l+1}, \cdots ,A_r$ を $h$ で置き換える

目次

• 小課題 1 想定解（解法 1-1 ）解説
• 小課題 2 想定解解説
• 満点解（解法 3-1 ）解説
• 遅延セグメント木とは？
• 別解（満点,解法 3-2 ）解説

小課題 1 想定解（解法 1-1 ）解説

思考手順はヒントをお読みください。

\(A_i\) を、左から \(i\) 番目のマスにおける最も高い水平な面の高さとします。レンガ \(i\) を積むことは、

\(L_i \leq k \leq R_i\) における \(A_k\) の最大値 \(M_i\) を求める

\(L_i \leq k \leq R_i\) における \(A_k\) を \(M_i+1\) で置き換える

で表せます。数列 \(\{ A_i \}\) を配列で持って、上の操作を愚直にシミュレートします。時間計算量は \(O(WN)\) です。

小課題 2 想定解解説

この小課題はボーナスです。対象の典型とは関係ありません。

解法 2-1

\(L_i,R_i\) を座標圧縮すると、小課題 \(1\) と同じ解法で時間計算量は \(O(N^2)\) になります。

解法 2-2

\(2\) つのレンガがそれぞれ覆う部分に、重なる部分があれば、この \(2\) つのレンガの上下の位置関係が決まります。 \(2\) つのレンガの組それぞれについてこれを求めます。そして、次のような DP で答えを求めます。

• \(N\) 要素の配列 \(A\) を用意し、各要素を \(0\) で初期化する

• \(i=1,2, \cdots ,N\) で以下を行う。

  • レンガ \(i\) とレンガ \(j\) の上下の位置関係が決まっている \(j\) \((j \lt i)\) それぞれについて、 \(A[i]\) を \( \mathrm{max} \{ A[i],A[j]+1 \}\) で置き換える。

これの各要素に \(1\) を足したものが答えです。

時間計算量は \(O(N^2)\) です。

レンガを頂点、この解法で求めた上下関係を有向辺としたグラフは、 DAG (有向非巡回グラフ) になります。

解法 2-3

C++ 言語で実装すると、小課題 \(1\) の実装でも時間制限に間に合うことがあります。時間計算量は \(O(NW)\) です。

満点解（解法 3-1 ）解説

思考手順はヒントをお読みください。

小課題 \(1\) と同様に、以下のことを行います。

\(L_i \leq k \leq R_i\) における \(A_k\) の最大値 \(M_i\) を求める

\(L_i \leq k \leq R_i\) における \(A_k\) を \(M_i+1\) で置き換える

これは後述の遅延セグメント木で高速にシミュレートできます。求める値は各 \(i\) における \(M_i+1\) です。

遅延セグメント木とは？

通常のセグメント木は、要素の列を、固定された二分木の構造で管理します。以下のような操作であって、ある条件（後述）を満たすものを、高速にシミュレート可能です。

• 列の内、 \(1\) つの要素を取得する
• 列の内、 \(1\) つの要素を変更する
• 列の内、連続した部分を、一定の演算で \(1\) つにまとめたものを求める

遅延セグメント木は、遅延評価をすることで、さらに次のような操作も可能にしたものです。

• 列の、連続した部分を、一定の規則で変更する

この問題では、演算は「最大値を選ぶ」で、変更の規則は上書きです。この場合、前計算 \(O(N)\) 時間、操作当たり \(O( \log N)\) 時間で実行できます。

AtCoder Library ( https://github.com/atcoder/ac-library ) に、遅延セグメント木を抽象化したもののライブラリ lazysegtree があります。このライブラリで利用できるテンプレート lazy_segtree (微妙に名前が異なります) がインターフェースです。

今回の問題では、以下のように設定します。

• S : 符号付き整数型
• op(S a, S b) : \( \mathrm{max} \{ a,b \} \) を返す
• e() : \(0\)
• F : 符号付き整数型
• mapping(F f, S a) : \(f=-1\) なら \(a\) 、それ以外なら \(f\) を（そのまま S として解釈して）返す
• composition(F f, F g) : \(f=-1\) なら \(g\) 、それ以外なら \(f\) を返す
• id() : \(-1\)

「ある条件」とは？

AtCoder Libraryのドキュメント ( https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html ) に記載されています。

大雑把に言うと、遅延セグメント木で正しく計算するには、次の条件を満たさなければなりません。

• op(op(a,b),c) \(=\) op(a,op(b,c))
• mapping(f,op(a,b)) \(=\) op(mapping(f,a),mapping(f,b))
• mapping(composition(g,f),c) \(=\) mapping(g,mapping(f,c))

lazy_segtree を使うときには、これが満たされていることを確かめましょう。

別解（満点,解法 3-2 ）解説

解法 \(2\)-\(2\) で求めた、上下関係の DAG を高速で求めます。実は、この DAG の辺は \(O(N)\) 本に減らせて、 \(O(N \log N)\) 時間で構築できます。ここでは詳細を省略しますが、類題として、第六回 PAST でこのテクニックが使える問題が出題されました。 ( https://atcoder.jp/contests/past202104-open/tasks/past202104_m )