Educational Codeforces Round 35 G. Mass Change Queries

お題箱より。

Problem - G - Codeforces

Editorialのコメント欄に色々別解が書かれているのですが、この記事はEditorial本文の解法を扱います。

問題概要

長さ $n$ の整数列 $a_{1}, ..., a_{n}$ が与えられる。この数列に対する操作が $q$ 個与えられ、これを順番に施す。

操作 $(l, r, x, y)$ ： $l \le i \le r$ である $i$ それぞれについて、もし $a_{i} = x$ であれば $a_{i} = y$ に置き換える。

操作完了後の数列を求めよ。

制約

$1 \le n \le 200000$
$1 \le a_{i} \le 100$
$1 \le q \le 200000$
各操作について、 $1 \le l \le r \le n$ かつ $1 \le x, y \le 100$

解法

「写像」として捉える

値の置き換えを「写像」として捉えます。この写像は「操作前に $x$ だった値は操作後に何になるか」というものを $x = 1, ..., 100$ について求めたものであり、長さ $100$ の配列として表現できます。

何も操作しないことを示す恒等写像は配列 $v = \lbrace 1, ..., 100\rbrace$ で表現し、「 $x$ を $y$ に置き換える」という操作の写像は恒等写像から $v\lbrack x \rbrack = y$ だけを変更したものになります。

そして操作を複数行うことは写像の合成に相当します。 $v_{1}$ で表現できる写像と $v_{2}$ で表現できる写像をこの順に適用するという合成写像は、値 $x$ が $x \to v_{1}\lbrack x \rbrack \to v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack$ と変化していくので、 $v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack$ の値を $x=1, ..., 100$ について並べた配列で表現できます。これを $v_{2}\circ v_{1}$ と表記することにします。

この写像の合成は結合法則を満たします。写像 $v_{1}, v_{2}, v_{3}$ について、 $(v_{3}\circ v_{2}) \circ v_{1}$ と $v_{3}\circ (v_{2} \circ v_{1})$ は等しくなります。これらはどちらも値 $x$ を $v_{3}\lbrack v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack \rbrack$ に変化させる写像であるからです。この性質は後で使います。

数列の位置を走査する

もし仮に全操作が全ての要素に適用される（つまり $l=1, r=n$ である）ならば、全ての操作を合成した写像を求めてしまえば全部の値の行き先がわかるので答えを求めることができます。

しかし実際の各操作では、それを数列 $a_{1}, ..., a_{n}$ のどの位置に適用するかという有効範囲 $\lbrack l, r \rbrack$ が指定されています。そのため位置によってそこに適用される写像が異なります。

なので位置を $i = 1, ..., n$ と順番に見ていきながら、「今見ている位置に適用されている操作を全て合成した写像は何か？」を求めていくことを考えます。これを実現するためには、各操作の有効範囲を出入りするタイミングでその操作の影響を足したり消したりする仕組みが必要です。そのためにセグメント木を利用します。

このセグメント木は長さが $q$ で、実装上は各ノードは長さ $100$ の配列を持ちます。 $k$ 番目の葉のノードは $k$ 個目の操作の写像に相当します。そして上位ノードではその下のノード2つの写像を合成した写像を保持することにします。

この写像の合成をセグメント木で処理できる理由として、先ほど確認した結合法則が効いてきます。単位元は恒等写像です。

こうすると「操作の影響を足したり消したりする」処理を実現できます。最初は全ての葉ノードを恒等写像にしておき、操作の有効範囲に入ったらその操作に相当する葉ノードの写像を変更し、有効範囲から出たらまた恒等写像に戻せば良いです。通常のセグメント木のように葉ノードを変更するたびにその上位ノードを更新していけば、最上位ノードでは今有効な操作を全て合成した写像が得られます。これで答えを求めることができます。

ただしこの解法では計算量がかなりタイトです。 $A = 100$ として1回写像を合成するたびに $O(A)$ かかるので、全体計算量が $O(Aq\log q + n)$ となります。