\(X_i\) が全て同じ値のとき

この等しい値を \(X\) とおきます。簡単のため、どの場所もいずれかの区間 \([L_i, R_i]\) に覆われているとすると、\(A\) の全ての値は \(X\) 以下でなければならず、区間 \([L_i, R_i]\) に関する条件は「\(A_{L_i}, \dots, A_{R_i}\) のいずれかが \(X\) に等しい」と言い換えられます。

このとき、条件を満たす \(A\) は次のような動的計画法によって数え上げることができます。

\(\text{dp}_{i, j} :=\) 数列の \(i\) 項目までを、\(R_k \leq i\) となるような区間 \([L_k, R_k]\) に対する条件を全て満たし、かつ \(X\) が最後に現れたのが \(j\) 項目であるように定める方法の総数。

これを in-place な動的計画法に書き換えると次のようになります。

• \(\text{dp}_j\) の値を \(\text{dp}_1, \dots, \text{dp}_{j-1}\) を用いて求める。
• \(R_k = j\) であるような区間に対する \(L_k\) の最小値を \(l\) として、\(\text{dp}_1, \dots, \text{dp}_{l-1}\) を全て \(0\) で置き換える。

累積和や尺取り法などを用いることで \(O(N + Q)\) で計算することができます。

元の問題に対する解法

\(A_i\) の上界を表す長さ \(N\) の数列 \(B = (B_1, \dots, B_N)\) を用意します。はじめ、\(B\) の全ての項は \(M\) とします。

\(j = 1, \dots, Q\) について、以下の操作を行います。

\(i = L_j, \dots, R_j\) について、\(B_i\) を \(\min(B_i, X_j)\) で置き換える。

これは双対セグメント木を用いれば \(O((N + Q) \log N)\) で計算することができます。

さて、\(\max(A_{L_i}, \dots, A_{R_i}) = X_i\) という条件について、\(B_{k} \lt X_i\) であるような場所を考慮する必要はありません。また、明らかに \(B_k \gt X_i\) であるような場所は \([L_i, R_i]\) に含まれません。そこで、\(X\) を固定し、\(B_k = X\) であるような場所のみに対して、\(X_i = X\) であるような条件のみを全て満たすように \(A_k\) の値を決めることを考えると、これは前節で説明した問題と同じです。この問題の答えを全ての \(X\) について求め、掛け合わせることで元の問題の答えが得られます。

\(B_k = X\) であるような場所を座標圧縮したのちに前節の解法を適用することで、全体で \(O((N + Q) \log N)\) で解くことができます。

実装例 (C++)