問題概要
$n$ 項からなる整数列 $H = \langle H_1, H_2, \dots, H_n \rangle$ が与えられる．各 $i$ ($1 \leq i \leq n$) について，次の条件を満たす $j$ ($i < j \leq n$) の個数を求め，列として出力せよ：
\begin{equation*}
\max_{ k \in ( i, j ) } H_k < H_j
\end{equation*}
制約
- $1 \leq n \leq 2 \times 10^5$
- $1 \leq H_i \leq n$
- $i \neq j \Rightarrow H_i \neq H_j$
解法
ある $i$ に対して，条件を満たす $j$ を（存在するとして）ひとつとります．このとき，$i < i' < j$ なる任意の $i'$ に対しても（条件において最大値を求める区間が狭くなることから）$j$ は条件を満たします．逆に $j$ を先に固定すれば，$j$ が条件を満たすような $i$ の集合は連続した（$\mathbb Z$ 上の）区間になり，その最小値 $\hat i$ を考えることができます．出力するべき列を $\langle R_i \rangle_{ i \in [ 1, n ] }$ とすれば，各 $j$ について $R[ \hat i, j )$ に対して一様に $1$ を加算すれば，欲しい列が求まります．
方針は見えた気がしますが，次の 2 つの部分問題を解かなければなりません：
- 固定した $j$ に対する $\hat i$ を求める．
- 区間への位置加算を高速に処理する（愚直にやると最悪ケースで $\Theta( n^2 )$ 時間になるため）．
それぞれについて考えていきます
$\hat i$ を求める
考察のため，$j$ を固定してから，条件において $\max$ をとる区間を左に伸ばしていくことを考えます．このとき，$H_i > H_j$ となるような $i$ がひとつでも区間内に入ってしまうとだめになるので，$i$ を降順に動かして最初に出現するそのような $i$ が $\hat i$ となります．
左に伸ばすのを毎回最初からやると TLE するので工夫する必要があります．やや天下り的ですが，スタックを使うことで高速に処理できます．具体的には，スタックには $H$ の添字を積むとして，各 $j$ に対して次のようにします：
- スタックトップの位置の値が $H_j$ 未満の間 pop する．
- スタックトップに残った位置が $\hat i$.
- スタックに $j$ を push する．
実際には，番兵として位置 $0$ に $\infty$ があるとした方が実装が簡単になる気がします．この場合，位置から $H$ の値を引ける（索引的な意味で）とは限らなくなるので，位置と値の組をスタックに積む方がよさそうです．
正当性ついてはざっくりですが，ある $j$ に対する処理で pop される要素は，それ以降に処理する $j'$ ($j < j'$) に対する処理において
- $H_j < H_{ j' }$ なら同様に pop されるべき．
- $H_j > H_{ j' }$ なら $H_j$ に阻まれて pop が止まるので $\hat i$ と関係無い．
ことなどから言える気がします．
この処理をするとき，各位置はスタックに対して一回ずつ push され，高々一回ずつ pop されるので，全体では $\Theta( n )$ 時間となります．
コード
constexpr auto INF = LIM<>::max() / 2; int main() { IN( int, N ); VI H( N ); cin >> H; stack< PII > stk; stk.EM( INF, 0 ); VI A( N + 1 ); REP( i, N ) { for ( ; stk.top().fst < H[i]; stk.pop() ); ++A[ stk.top().snd ]; --A[ i + 1 ]; stk.EM( H[i], i + 1 ); } partial_sum( ALL( A ), begin( A ) ); A.erase( begin( A ) ); cout << A << endl; return 0; }
main = getLine >> readInts >>= printList . tail . scanl1 (+) . solve solve hs = elems $ runSTArray $ do let n = length hs stack <- newSTRef [ ( maxBound, -1 ) ] ary <- newArray ( -1, n - 1 ) 0 forM_ ( zip [ 0 .. ] hs ) $ \( j, h ) -> do modifySTRef stack $ dropWhile ( ( < h ) . fst ) i <- snd . head <$> readSTRef stack modifyArray ary i succ modifyArray ary j pred modifySTRef stack ( ( h, j ) : ) return ary
