問題概要
整数 $N$ と，長さ $N$ の整数列 $A = (A_0, \ldots, A_{N - 1})$ が与えられる． $A$ を 2箇所で区切って，3個の空でない連続する部分列に分解するとき， おのおのの部分列に含まれる数の種類数の和の最大値を求めよ．
制約
$3 \leq N \leq 3\times10^5$，$1 \leq A_i \leq N$
解
略解．click to open
- $L_i := (A_0, \ldots, A_{i - 1})$ に含まれる種類数
- $R_i := (A_i, \ldots, A_{N - 1})$ に含まれる種類数
- $dp[i][j] := (A_0, \ldots, A_{j - 1})$ と $(A_j, \ldots, A_{i - 1})$ に含まれる種類数の和 ($j \in [0, i)$)
とする．求める値は $\max_i (R_i + \max_j(dp[i][j]))$．
$L_i$ と $R_i$ は，端から一つずつ見ていって作れる．
$dp[i]$ と $dp[i + 1]$ はだいたい同じだが，$A_k = A_{i + 1}$ ($k < i + 1$) となる最大の $k$ をとると， $j < k$ のときには $dp[i + 1][j] = dp[i][j]$ で，$k \leq j$ のときには $dp[i + 1][j] = dp[i][j] + 1$ なので， $dp[i + 1]$ は，$dp[i]$ から区間加算で作れる．区間加算と最大値を取得する遅延セグメント木を使えば解ける．