分割統治を用いて、時間計算量 \(O(N\log(N)^{2})\) で解けます。

この解法の計算量は \(K\) に依存しません。また、\(P\) が順列でなくとも解けます。

つまり、本題を包含する以下の問題を解くことができます。

長さ \(N\) の非負整数列 \(A = (A_{1}, A_{2}, \dots ,A_{N}), B = (B_{1}, B_{2},\dots, B_{N})\) と整数 \(K\) が与えらえます。以下の条件を全て満たす整数組 \((L, R)\) の数を求めてください。

• \(1\leq L\leq R\leq N\)
• \(\displaystyle\max(A_{L}, \dots, A_{R}) - \min(A_{L}, \dots, A_{R})\leq K + \sum_{i = L}^{R - 1}B_{i}\)

以下の問題が \(O(N \log(N))\) で解くことができれば、分割統治を用いて前述の計算量を達成できます。

数列 \(A = (A_{1}, A_{2}, \dots A_{N})\) と \(1\) 以上 \(N\) 以下の整数 \(M\) が与えられます。以下条件を全て満たす整数組 \((L, R)\) の数を求めてください。

• \(1\leq L\leq M\)
• \(M\leq R\leq N\)
• \(\max(A_{L}, \dots, A_{R}) - \min(A_{L}, \dots, A_{R})\leq K + R - L\)

\(L\) を fix します。そして、 \(Lmax, Lmin\) を以下のように定義します。

• \(Lmax = \max(A_{L}, \dots , A_{M})\)
• \(Lmin = \min(A_{L}, \dots, A_{M})\)

そして、\(r1, r2\) を以下のように定義します。

• \(Lmax = \max(A_{L}, \dots , A_{R})\) を満たす最大の整数 \(R\) を \(r1\) とする。
• \(Lmin = \min(A_{L}, \dots, A_{R})\) を満たす最大の整数 \(R\) を \(r2\) とする。

ここで、 \(r1 \leq r2\) であるとします。(\(r1 > r2\) である場合も同様に解けます)

これらの変数を用いいると、以下の条件のいずれかを満たす \(R\) を数え上げれば良いことになります。

• \(M\leq R\leq r1\) かつ \(Lmax - Lmin \leq R - L + K\)
• \(r1< R\leq r2\) かつ \(\max(A_{M}, \dots, A_{R}) - Lmin \leq R - L + K\)
• \(r2 < R \leq N\) かつ \(\max(A_{M}, \dots, A_{R}) - \min(A_{M},\dots , A_{R}) \leq R - L + K\)

これらの式は、\(L\) に依存する値と \(R\) に依存する値は存在しますが、\(L, R\) どちらにも依存する値は存在しないため、\(a\leq R \leq b\) かつ \(f_{k}(L) \leq g_{k}(R)\) という形に条件を置き換えることができます。

つまり、固定された数列 \(C = (C_{1}, C_{2}, \dots , C_{|C|})\) に対して、\(C_{l}, C_{l + 1}, C_{r}\) の中で \(v\) 以上の値は何個ありますかというオフラインクエリに置き換えることができます。これは segmettree で \(O(N\log(N))\) で解くことができます。

実装例 c++ 356 ms