セグ木とか必要なくて、本当に単純な実装で解けるの面白い
問題
制約
考えたこと
まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。
カッコ列の連想から、次の判定手順が自然に得られた。
スタックを用意する。
数列を後ろから見ていくことにする。今見ている要素が であるとき
ならば、スタックに
を挿入する
ならば、階段になっている限りスタックを pop していく (たとえば、スタックが top から順に 2, 3, 4, 6, ... だとしたら、
に対して操作したあとのスタックは top から順に 6, ... となる)
最終状態において、スタックが空であることが、生成可能であるための必要十分条件である。
これで判定は解けた。
数え上げ
一般に、区間 が生成可能ならば、
に対して区間
も生成可能である。
よって、上に述べたようなスタックの処理をしながら、
であるような
に対して
- スタック操作後のスタックの先頭要素の添字を
として (空なら
として)、
を答えに合算していく
とすることで問題が解ける。計算量は となる。