AGC056B-Range Argmax

解説の補足程度

基本方針

各 $x$ について、 $x$ を作る $p$ のうち辞書順最大のものと一対一対応をさせる
これにより、そのような $p$ を数え上げる問題になる

以下0-indexed

$p$ の値を降順に決めていくことを考える
つまり、 $p^{-1}(N-1),p^{-1}(N-2),...,p^{-1}(0)$ を前から決めていく
上から決めていくことで、使用した index を含む各区間は $x$ の値が決まっていることになる

$p^{-1}(9)=4$ とした時の例
f:id:drogskol:20211205114458j:plain
上の例では、 $4$ を含む２つの区間は $x$ の値が決まったことになる
したがって、[0,3]と[5,9]についての問題に出来たように見える
（p[0,3]=[5,8] p[5,9]=[0,4] のように使う）

しかし、このような key が $O(N^2)$ の区間DPでは辞書順最大でない $p$ も数えてしまう
（中略）
したがって、 $p(i)=8$ として良い $i$ は、 $4$ を含む区間に含まれている必要がある
つまり、上の例では [0,3]で最大値のindexが2以上と[5,9]についての問題に帰着される
そこで、
dp[l][r][m]:[l,r]の順列で最大値のindexがm以上となるものの個数
という区間DPを考える
遷移を $O(1)$ で行えれば良く、以下の式変形に注目する