$N$要素からなる順列$P$について、$N(N+1)/2$個の区間に対して最小値の分布を求める(最小値が$i$となるような区間はいくつあるか?)。
最小値が$i$となるような区間の数は、$i$の左右で$i$より小さい最初の要素がどこにあるかがわかれば計算できる。たとえば
5 4 8 1 2 6 7 3
という順列では、6の左右で6より小さい要素は左の2,右の3であり、2と3の間で6を含む区間の数は2つである。ここから、6が最小値となるような区間の数は2つであることがわかる。
各要素に対して、左右で自身より小さい最初の要素を愚直に求めようとするとO($N^2$)だが、std::setを使うとO(NlogN)にできる。要素$i$が出現するindexをidx[i]として記録しておき、idx[1]から順にstd::setに入れていく。要素$i$を見ているとき、std::setには$i$より小さい要素のindexのみが入っているので、$i$の左右で$i$より小さい最初の要素は二分探索で求められる。これをすべての$i$に対して行いながら区間の数を数えればよい。