Codeforces Round #531 (Div. 3)E. Monotonic Renumeration

問題概要

長さ $n$ の数列 $a$ に対し, 長さ $n$ の数列が以下の条件を満たすとき $b$ は Monotonic Renumeration であるという :

$b_1 = 0$
$1 \le i \le j \le n$ である $i, j$ に対して $a_i = a_j$ ならば $b_i = b_j$ が成り立つ(逆, つまり $b_i = b_j$ ならば $a_i = a_j$ は成り立たなくてもよい).
任意の $1 \le i \le n-1$ に対して $b_i = b_{i+1}$ もしくは $b_i +1 = b_{i+1}$ が成り立つ.

与えられた $a$ に対して, Monotonic Renumeration な $b$ は何通り存在しますか？ $998244353$ で割った余りを答えてください.

制約

$1\le n \le 2\times 10^5$
$1 \le a_i \le 10^9$

解説

三つ目の条件から, 数列は広義単調増加でなければならないことがわかります. また更に $a_i = a_j$ のとき $b_i = b_j$ でければなりませんから, これをみたしながら単調増加を保つには $a_i = a_j$ のとき $b_i = b_{i+1} = \cdots = b_{j-1} = b_j$ でなければなりません. この条件を満たさなければならない区間は一つにまとめてしまえば, 独立な区間の数を $x$ として $2^{x-1}$ が答えとなります(次の区間に割り当てる数字は同じ値か $1$ 増やした値のいずれかから選べるためです).

そこで独立な区間の数を上手に数えることにしましょう. ここでは, Union-Find を用いた方法を考えます. まずは大きさ $n$ の UF を用意します.

$i = 1$ から順にみていくことにして, $a_i = a_j, j \lt i$ をみたすような $i$ を見つけたら, $j, j+1, \cdots , i$ をすべてマージすることにしましょう. これを実装すれば集合の個数が独立な区間の個数になってくれますが, このままだと O(n^2) かかって TLE します. どうすればいいでしょうか？

これは, $j, j+1, \cdots , i$ をすべてマージする過程で, 途中にすでにマージされた区間があった場合に飛ばすような処理を追加すればよいです. 具体的には次のように実装します:

$cur = i$ として初期化する.
$cur - 1$ と $cur$ の $root$ が異なるなら $cur-1$ と $cur$ をマージして $cur =cur-1$ , 同じなら $cur = root(cur-1)$ へと移動
$cur$ が $j$ になったらループを抜ける.

このように実装すると, 各頂点を見る回数が高々 $2$ 回に抑えることができます. ただしこれを行うには $root$ が常に集合の中での最小の頂点番号にする必要があるので, UF の計算量は $log(n)$ になります(が, 十分高速です). ACLを使っているなら, 若干実装をいじる必要があります.

実装

ACL の dsu に新しい関数を追加して上記の実装をしています.

Submission #145840484 - Codeforces