問題概要
サイズ $n$ の順列 $P = \langle P_1, P_2, \dots, P_n \rangle$ が与えられる．$P$ の連続部分列 $A$ であって，以下の条件を（全て）満たすものの個数を求めよ：
- $|A| \geq 4$
- $A_1 < A_2$
- $\exists! i \in [ 2, |A| - 1 ] \cap \mathbb Z, A_{ i - 1 } < A_i > A_{ i + 1 }$
- $\exists! i \in [ 2, |A| - 1 ] \cap \mathbb Z, A_{ i - 1 } > A_i < A_{ i + 1 }$
制約
- $4 \leq n \leq 3 \times 10^5$
準備
列 $A$ の $l$ 項目から $r$ 項目までを取り出してできる連続部分列を $A[ l, r ]$ と書くことにします．
解法
どういう列を数えたいか噛み砕くと，
- 増加・減少が切り替わる箇所がちょうど $2$ 箇所．
となります．増加から減少に切り替わる位置を $x$, 減少から増加に切り替わる位置を $y$ とすると，
- $A_1 < A_2$ より $x < y$．
- $A[ 1, x ]$ は単調増加．
- $A[ x, y ]$ は単調減少．
- $A[ y, |A| ]$ は単調増加．
です．
条件を満たすある部分列 $A$ において $x, y$ として取られる可能性がある添字は $P$ においても増加・減少が切り替わる位置なので，$P$ を走査して連続する $3$ 要素の大小関係を見ることで事前に列挙できます．このように列挙した添字（を昇順に並べたもの）を $I$ とすると，各 $i \in [ 1, |I| - 1 ] \cap \mathbb Z$ について，$P[ I_i, I_{ i + 1 } ]$ は，$P$ の単調増加な連続部分列であって極大なものか，$P$ の単調減少な連続部分列であって極大なもののいずれかです．$P[ I_i, I_{ i + 1 } ]$ が単調減少となるような $i \in [ 1, |I| - 1 ] \cap \mathbb Z$ について，$P[ I_i, I_{ i + 1 } ]$ の左右から単調増加列を伸ばすことで得られる列が，数えたい列です．
$P[ I_i, I_{ i + 1 } ]$ が単調減少だとします．この左側に単調増加列を伸ばす（伸ばす方向と増加の方向が逆なことに注意）と考えると，最大限伸ばしたときの左端は減少から増加に切り替わる位置か，$P$ の先頭のいずれかなので，$i > 1$ ならば $I_{ i - 1 }$ で，そうでなければ $1$ です．同様に右側についても，$i < |I| - 1$ ならば $I_{ i + 2 }$ で，そうでなければ $n$ です．このままだと場合分けが煩雑ですが，$P$ の先頭に $n + 1$ を，末尾に $0$ を追加して得られる列 $\langle n + 1, P_1, P_2, \dots, P_n, 0 \rangle$ に対して上記のことを考えると，$i > 1$ と $i < |I| - 1$ が保証されるので場合分けを消せます．すると，左に伸ばす左端の候補は $I_{ i - 1 }, I_{ i - 1 } + 1, \dots, I_i - 1$ の $I_i - I_{ i - 1 }$ 通りで，右に伸ばす右端の候補は $I_{ i + 1 } + 1, I_{ i + 1 } + 2, \dots, I_{ i + 2 }$ の $I_{ i + 2 } - I_{ i + 1 }$ 通りとなるので，この $i$ に対して条件を満たす部分列の個数は，
\[
( I_i - I_{ i - 1 } ) \times ( I_{ i + 2 } - I_{ i + 1 } )
\]
となります．後は，$P[ I_i, I_{ i + 1 } ]$ が単調減少であるような全ての $i$ について上記の値を計算して和をとることで答えが求まります．
このアルゴリズムは，番兵の挿入と $I$ の構築に $\Theta( n )$ 時間（$P$ を std::vector でもつ場合）かかり，答えの計算に $O( n )$ 時間かかります．従って全体では $\Theta( n )$ 時間であり正答できます．
コード
int main() { IN( int, N ); VI P( N ); cin >> P; MAP_PRED( P ); P.insert( begin( P ), N ); P.PB( -1 ); VI indices; REP( i, 1, N + 1 ) { if ( ( P[ i - 1 ] < P[i] ) != ( P[i] < P[ i + 1 ] ) ) { indices.PB( i ); } } LL res = 0; for ( int i = 1; i + 2 < SZ( indices ); i += 2 ) { res += LL( indices[i] - indices[ i - 1 ] ) * ( indices[ i + 2 ] - indices[ i + 1 ] ); } cout << res << endl; return 0; }
