AtCoder Beginner Contest 352, D : Permutation Subsequence

問題文

　https://atcoder.jp/contests/abc352/tasks/abc352_d

問題概要

　サイズ $n$ の順列 $P = \langle P_1, P_2, \dots, P_n \rangle$ が与えられる．
　$k$ 項からなる $P$ の添字列 $I = \langle I_1, I_2, \dots, I_k \rangle$ であって，以下の 2 条件を満たすものを考える．

• $1 \leq I_1 < I_2 < \dots < I_k \leq n$
• $\langle P_{ I_1 }, P_{ I_2 }, \dots, P_{ I_k } \rangle$ は連続する整数からなる．

　条件を満たす添字列 $I$ の内，$I_k - I_1$ を最小化したときのその値を求めよ．

制約

• $1 \leq k \leq n \leq 2 \times 10^5$
• $1 \leq P_i \leq n$
• $i \neq j \Rightarrow P_i \neq P_j$

解法

　$P$ を走査したりして条件を満たす添字列を作るのはむずかしそうに思えるので，添字列の方に着目して考えます．満たすべき条件をよく読み解くと，
\begin{equation*}
i < j \Leftrightarrow P_{ I_i } < P_{ I_j }
\end{equation*}
を満たしているはずです．なので，$P_{ I_i }$ の昇順に添え字を並べた列を $\hat I$ とすれば，条件を満たす添字列は $\hat I$ の連続する $k$ 項の部分列として現れるはずです．よって，$\hat I$ を作ってから $\hat I$ の連続する $k$ 項それぞれの最大値・最小値を求められれば問題を解けることになります．$\hat I$ を構成するには，各 $i$ について
\begin{equation*}
\hat I_{ P_i } := i
\end{equation*}
とすればよいです．
　次に，$\hat I$ の連続する $k$ 項の最大値・最小値をそれぞれ求めたいわけですが，愚直に求めようとするとひとつあたり線形時間かかって全体で $\Theta( n^2 )$ 時間になるケースを作れてしまうのでもうひと工夫必要です．
　先頭の $k$ 項は愚直に舐めることにして，その $k$ 項をなんらか（後述）のデータ構造 $S$ に入れて管理することを考えます．先頭の $k$ 項を格納した $S$ から，第二項からの $k$ 項に作り変えるには，$S$ から $I_1$ を削除し，$I_{ k + 1 }$ を挿入すればよいです．元々の目的と併せて $S$ に求められる要件は，

• 値の追加ができる．
• 値の削除ができる．
• 最大値を取得できる．
• 最小値を取得できる．

となります．これらの操作をある程度高速にできれば何でもよいといえばよいのですが，C++ では std::multiset があるのでこれを使うのが楽だと思います．

コード

int main()
{
	IN( int, N, K );
	VI P( N );
	cin >> P;
	MAP_PRED( P );

	VI indices( N );
	REP( i, N )
	{
		indices[ P[i] ] = i;
	}

	multiset< int > s;
	REP( i, K )
	{
		s.insert( indices[i] );
	}
	int res = *rbegin( s ) - *begin( s );
	REP( i, K, N )
	{
		s.erase( s.find( indices[ i - K ] ) );
		s.insert( indices[i] );
		chmin( res, *rbegin( s ) - *begin( s ) );
	}
	
	cout << res << endl;

	return 0;
}