問題概要
$n$ 項の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．
$A$ の（連続するとは限らない）部分列であって，隣接する 2 項の差の絶対値が $d$ 以下なものの長さの最大値を求めよ．
制約
- $1 \leq n \leq 5 \times 10^5$
- $1 \leq A_i \leq 5 \times 10^5$
- $0 \leq d \leq 5 \times 10^5$
解法
ある $A_i$ を末尾とする部分列について考えると，$\langle A_1, A_2, \dots, A_{ i - 1 } \rangle$ から作られる部分列に $A_i$ を連結した形をしています．ここで，手前から選んでくる部分列は，$A_i$ をくっつけられるものの内最長のものをとってくるのが最適となります．部分列を採用できるかどうかはその末尾要素のみによって決まるので，次のような動的計画法を考えることができます：
\begin{equation*}
\mathit{ dp }[i][j] = \text{$\langle A_1, A_2, \dots, A_i \rangle$ から作れる部分列で，末尾が $j$ であるものの長さの最大値}
\end{equation*}
考えることはできるのですが，このままだと $\Theta( n \max A )$ 空間が必要になって無理なので，まずは次元を削減します．DP の漸化式を考えると
\begin{equation*}
\mathit{ dp }[i][j] = \begin{cases}
0 & \text{($A_i \neq j$)} \\
\max\limits_{ A_i - d \leq j \leq A_j + d } \mathit{ dp }[ i - 1 ][j] + 1 & \text{(otherwise)}
\end{cases}
\end{equation*}
となっています*1*2．更新する際の手順を考えてみると，$\max\limits_{ A_i - d \leq j \leq A_j + d } \mathit{ dp }[ i - 1 ][j]$ を求めた後は $\mathit{ dp }[ i - 1 ]$ の行は必要無くなるので，
\begin{equation*}
\mathit{ dp }[i] = \text{$A$ を舐める過程のある時点で）末尾が $i$ である部分列の長さの最大値}
\end{equation*}
として配列を使い回すことができます．
空間の問題は解決しましたが，時間に関してはまだ問題があって，$\Theta( n d )$ 時間がかかってしまっています．$n$ に関してはどうしようもなさそうなので $d$ について考えてみると，これは「区間中の最大値を求める処理」に由来しています．実はこれは Range Maximum Query (RMQ) と呼ばれるようなもので，セグメント木というデータ構造を使うと
- 列上の一箇所を更新する．
- 列上の区間の最大値を求める．
が $O( \log \text{列の長さ} )$ 時間で行えることが知られています．よって，先程の DP の DP テーブルをセグメント木に載せることで，最大値を求める処理を $O( \log \max A )$ 時間に改善するとができ，全体では $O( n \log \max A )$ 時間となって間に合わせることができます．
セグメント木の実装については，自分で用意してもよいですし，最近*3では AtCoder Library (ACL) を利用することもできます．
コード
// セグメント木による Range (Minimum|Maximum) Query template < typename T = int, typename F = std::less< T >, T identity = std::is_same< F, std::less< T > >::value ? std::numeric_limits< T >::max() : std::numeric_limits< T >::min(), typename = typename std::enable_if< std::is_same< F, std::less< T > >::value || std::is_same< F, std::greater< T > >::value >::type > class RangeMQuery; // 中身省略 // RangeMQuery< comp = less, identity element = inf >( N ) // RangeMQuery< comp = less, identity element = inf >( VT src ) // update( pos, x ) // query( [ a, b ) ) int main() { IN( int, N, D ); VI A( N ); cin >> A; RangeMQuery< int, greater< int > > rmq( M + 1 ); REP( i, N ) { const int l = max( 0, A[i] - D ); const int r = min( M, A[i] + D ); const int len = rmq.query( l, r + 1 ); rmq.update( A[i], len + 1 ); } cout << rmq.query( 0, M + 1 ) << endl; return 0; }
