ABC470 G - ΣШX

考え方

まず、右端が指定位置にあるもののみを数えることを考えてみる。

$0$ から $N$ までの各数がその右端以前で最後に登場する位置を 1-indexed で確認する。
それの累積最小値を考えると、$k$ 以下の数を全て含む区間の個数がわかる。
これの総和を考えると、最小除外数が $k$ である範囲は $0$ から $k-1$ まで $k$ 回分カウントされる。
つまり、結果として最小除外数の値を足したことになる。

$1$ つの右端指定で素直にこれを処理すると計算量は $O(N)$ である。
よって、全体で $O(N^2)$ でよければこれで解けた。
問題はこれをどうやって高速化するか。

右端を $1$ つ進めると、最終登場位置自体は $1$ ヶ所を大きい値に更新するだけである。
しかしその場合、累積最小値の更新が難しい。
元々入っていた値のせいでつぶされていた情報の復元が難しいからである。

ということは、逆なら可能な可能性がある。
つまり、右端を $1$ つ戻すと、最終登場位置自体は $1$ ヶ所を小さい値に更新する。
その場合、累積最小値は、そこより後ろを全て最小値更新すればいい。

これを可能にするには、lazy segment木で、範囲代入と区間和と二分探索ができればよい。
加えて、各数の登場位置をバケツソートの考え方で管理する。

例えば、$3$ の最終登場位置が $8$ から $6$ に更新された場合、以下の手順で更新する。

• $3$ の登場位置一覧の末尾の $8$ を削除し、$6$ を新しい末尾にする
• segment木上で、$3$ 以降の範囲で、$6$ 以上の値が入っているところを二分探索する
  • 累積最小値は、必ず広義単調減少であるため、二分探索が可能である
• 見つけた範囲に、$6$ を範囲代入する

これで計算量は、$1$ 回の処理が $O(\log N)$ で済み、全体で $O(N\log N)$ となる。

入力例2での動作

入力を受け取る。

n: 6
a: {2, 1, 0, 2, 1, 4}

まず、右端を $6$ 番目に固定する。
各値の登場位置を 1-indexed で並べ、番兵として先頭に $0$ を入れると次のようになる。

0: {0, 3}
1: {0, 2, 5}
2: {0, 1, 4}
3: {0}
4: {0, 6}
5: {0}
6: {0}

各値の最終登場位置の累積最小値を、segment木の $0$ から $6$ の葉に持つ。
右端が $6$ 番目のときは次の状態になる。

{3, 3, 3, 0, 0, 0, 0}

この $7$ 個の値の和 $9$ が、右端を $6$ 番目に固定した区間の mex の総和である。

右端を後ろから $1$ つずつ戻すと、葉の状態と加算する値は次のように変化する。

例えば、右端を $5$ 番目から $4$ 番目へ戻すときは、位置 $5$ にある値 $1$ を取り除く。
値 $1$ の最終登場位置は $5$ から $2$ に変わるので、葉 $1$ 以降で値が $2$ より大きい部分を $2$ に更新する。
その結果、葉は $(3,2,2,0,0,0,0)$ となる。

同様に右端を $3$ 番目から $2$ 番目へ戻すときは、値 $0$ の最終登場位置が $3$ から $0$ になる。
累積最小値も全て $0$ になり、それ以降の寄与は $0$ である。

したがって、全ての右端についての総和は $31$ となる。

注意点

答えや segment木で持つ区間和は、int 型からはみ出る。
long long 型を用いること。

別解

特になし。