問題

考え方

式だけみるとぱっと何を求められているかわからないので、まずはナイーブに $O(N^3)$ の実装で実験してみる。そうすると区間の数について最小になる要素を求めて、その総和を求める問題であることが分かる。

さて、区間の数をまとめて計算したい。「最小値が $i$ になる区間が数列上にいくつ存在するか？」という問題を考える。これが高速に求められれば $i$ と区間の数 $cnt$ を掛けて、その総和を計算すれば良い。

サンプル3を例に考える。数列は以下のように与えられている。1-indexed で考えていくことにする。番兵として一番右と左に -1 があることにする。

8
-1 5 4 8 1 2 6 7 3 -1

このとき数列の要素 $2$ が最小値になる開区間の左端と右端の index はどこになるか、というと左端の値は $a_4=1$ で $4$ 、右端は $a_9 = -1$ で $9$ となる。 $a_5=2$ であるから、区間の左端の候補の数は $5-4$ で右端の候補は $9-5$ である。よって $(5-4) * (9-5) = 4$ 個の区間で最小値が $2$ になることが分かる。

ある値 $k$ を考えたときに $k$ 未満の要素の右端の最大の index と左端の最小の index を求める必要がある。これは値の小さい値から数列上の index を TreeSet に含めていくようにして求めていくと、求める前には必ず今考えようとしている $k$ よりも小さい数の index しか TreeSet 上に存在しないので左端と右端の index が $O(logN)$ で求められることになる。