コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 2187 (記事作成時点)
供養
解法
- 取り出し方が一意に定まるような長さ $k$ の部分列の添字列を $x_{1} \lt \dots \lt x_{k}$ としたとき、先頭と最後に $x_{0} = 0, x_{k + 1} = N + 1$ を追加した$0 = x_{0}, x_{1}, \dots, x_{k}, x_{k + 1} = N + 1$ について考える
- このとき、部分列の取り出し方が一意であるためには $1 \le i \le k$ について、$A_{x_{i - 1} + 1}, \dots, A_{x_{i + 1} - 1}$ の中で $A_{x_{i}}$ と同値の要素は $A_{x_{i}}$ 以外に存在しないことが必要
- $A$ の先頭から $i$ 番目の要素まで見たときに、$A_{i}$ を含み、かつ取り出し方が一意に定まる部分列の種類数を $P_{i}$ とする
- $A_{i}$ と同値の要素で、$A_{i}$ 以前に最後に登場した位置を $i^{'}$ とすると、$i^{'} \le j \lt i$ のうち $j + 1, \dots, i - 1$ に $A_{j}$ と同値のものは存在しないような $j$ について $P_{j}$ を合計したものが $P_{i}$ となる
- 上記を求める手法は以下の通り
- $C_{A_{i}}$ を値が $A_{i}$ の要素が $i$ より前に最後に登場した位置とする
- $P_{0} = 1$ とする
- $P_{i} = \sum_{j = C_{A_{i}}}^{i - 1}P_{j}$ とする
- $P_{C_{A_{i}}} = 0$ とする
- 最終的に $\sum_{i = 1}^{N}P_{i}$ が答え
実装
計算量は $O(N \log N)$
公式解説
躓いた点
- BITで管理する発想が出てこず、DPで解こうとして失敗
