逆操作の導入

突然ですが，操作が chmax,chmin ではなくて代入であったならば，どのような解法が一般的でしょうか？逆操作を考えることが重要なのでした. 代入に関する操作・逆操作の対応は次のようになります.

• 代入操作 : \(z\) に \(q\) を代入する. 結果として \(z=w\) になる.
• 代入の逆操作 : \(q\) が \(w\) に match する仮定のもと，\(w\) を \(\ast\) に置き換える. 結果として \(z\) が \(w\) に match する.
  • \(\alpha\) が \(\beta\) にマッチするとは，\(\alpha=\beta\) または \(\beta=\ast\) が成り立つことをいう.

より一般的に操作列を考える文脈では，次のようなことを考えて対応を取っていました.

• 操作列を前から見る : 初期状態から操作列の prefix を適用して，現在の状態を得る. 最終的な現在の状態が目標状態に一致する.
• 操作列を後ろから見る : 現在の状態から操作列の suffix を適用して目標状態になるための，現在の状態に対する条件を得る. 最終的な現在の状態に対する条件を，初期状態が満たす.

本問題も，このフレームワークを適用して考察を進めることができます. ここで代入操作の例を出したのは気まぐれというわけではなく，実は chmax,chmin の列は代入を表すことができるのです : \(a\ge b\) として，\(a\) で chmax した後に \(b\) で chmin することは，\(b\) を代入したことと同じです.

よく観察すると，chmin,chmax を組み合わせなくとも代入を表現できることがあります. たとえば \(z\le a\) においては，\(z\) を \(a\) で chmax することは，\(z\) に \(a\) を代入することと同じです. このことは，代入の逆操作で登場した \(\ast\) の考え方の中間に位置するような，「\(z\le a\) であれば任意」あるいは「\(z\ge b\) であれば任意」のような概念の登場を示唆しています. 本問題の考察の初手が分からなかった人は，chmax,chmin の逆操作の特徴付けを整理して，もう一度この問題に取り組んでみてください. 次節では天下り的に解法を与えてしまいます.

本問題の解法

操作回数の制限を忘れ，有限回の操作で \(A\) を \(B\) に一致させられるかどうかを検討します.

操作列を後ろから見ます. ここでの状態は，操作対象となる長さ \(N\) の整数列のことを指します. 現在の状態 \(A'\) に対する条件として，整数列 \(L=(L_1,L_2,\dots, L_N),R=(R_1,R_2,\dots, R_N)\) を持ちます. \(L,R\) は次のことを表しています : \(\forall i, A'_i\in [L_i,R_i]\) を満たすことが，\(A'\) にこれまでに確定させた操作列の suffix を適用したときに \(B\) に一致するための必要十分条件である. これまでに確定させた操作列の suffix が空であるとき，明らかに \(L_i=R_i=B_i\) です. 現在の状態を保持するのではなくて，あくまでもそれに対する条件を保持していることに注意してください.

chmax \(l\) \(r\) では，\(x\coloneqq X_{r-l+1}\) とおくと，各 \(i\in [l,r]\) に対して \(A_i\leftarrow \max(A_i,x)\) とするのでした. これの逆操作は次のように特徴付けられます.

• 適用可能である条件 : 各 \(i\in [l,r]\) に対して \(x\le R_i\) が成り立つ.
• 適用した後の現在の状態に対する条件の変化 : 各 \(i\in [l,r]\) に対して独立に，\(L_i\le x\) が成り立つとき \(L_i\leftarrow -\infty\) とする.

chmin \(l\) \(r\) では，\(y\coloneqq Y_{r-l+1}\) とおくと，各 \(i\in [l,r]\) に対して \(A_i\leftarrow \min(A_i,y)\) とするのでした. これの逆操作は次のように特徴付けられます.

• 適用可能である条件 : 各 \(i\in [l,r]\) に対して \(y\ge L_i\) が成り立つ.
• 適用した後の現在の状態に対する条件の変化 : 各 \(i\in [l,r]\) に対して独立に，\(R_i\ge y\) が成り立つとき \(R_i\leftarrow \infty\) とする.

\(L_i\in \lbrace -\infty,B_i\rbrace, R_i\in \lbrace B_i,\infty\rbrace\) が成り立ちます. ここで \(\infty\) は形式的な記号で，十分大きな値であることを表します. 必要ならば \(\infty\) を \(N\) と読み替えても構いません.

各 \(i\) に対して，\(L_i\leftarrow -\infty\) が初めて行われるとき，これを \(i\) に対する 下側緩和とよびます. 同様に，\(R_i\leftarrow \infty\) が初めて行われるとき，これを \(i\) に対する 上側緩和とよびます. 下側緩和と上側緩和をまとめて緩和とよびます.

各 \(i\) に対して，区間 \([L_i,R_i]\) は単調に増加します. よって，各操作は，一度適用可能になると，それ以降適用可能であり続けます. また，適用可能である逆操作によって緩和されなかった \(i\) は，どの逆操作の列に対してもその逆操作によって緩和されることはないことも分かります. したがって，各逆操作は高々 \(1\) 回行うとしてよいです. さらに，適用可能な逆操作はどの順番で行ってもよく，結果として最も緩和された条件 \((L,R)\) が一意に定まります. この \((L,R)\) が \(\forall i, A_i\in [L_i,R_i]\) を満たすことが，操作を繰り返して \(A\) を \(B\) に一致させることができる条件となります.

ここまでで，操作回数・計算量を気にしない実直な解法が得られています. まだ行っていない適用可能な逆操作が存在する限り，それを行うことを繰り返せばよいです.

操作回数について考えます. 緩和を起こさない逆操作は行う意味がありません. 緩和は上側緩和と下側緩和で合わせて \(2N\) 種類しかありません. したがって，無駄な逆操作を省けば操作回数は自然に \(2N\) 回以下になります.

計算量について考えます. 各逆操作 op \(l\) \(r\) に対して，それを適用可能でなくしている \(i\in [l,r]\) の個数，たとえば op が chmax のときは \(i\in [l,r], x\gt R_i\) を満たす \(i\) の個数を保持しておきます. まだ行っていない適用可能な逆操作を集めた queue を用意し，逆操作で緩和が起こるたびに，適用可能でなくしている \(i\) の個数のテーブルを更新し，適宜適用可能になった逆操作を queue に入れていくことを繰り返せばよいです. 各緩和に対して \(O(N^2)\) time で愚直に更新しても，緩和は \(O(N)\) 回しか起こらないので，あわせて \(O(N^3)\) time で実行できます.

以上の解法は \(O(N^3)\) time / \(O(N^2)\) space で動作します.