ACL Beginner Contest E - Replace Digits

先日、AtCoder Libraryの遅延伝播セグメント木の使い方について記事を書きました。

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

今回の問題はセグ木にちょっと変なものを乗せる問題なので、上記の記事で解説していることの実践編として書いていこうと思います。この記事を読む前に上記の記事を読むことをオススメします。

解法

区間更新クエリと全体取得クエリを処理する問題です。遅延伝播セグメント木に乗せることを考え、まずは各ノードの data として何を持てば良いかを考えます。後で足りない情報があれば足すとして、まずは一番大事な「各桁の値」をどう持つか考えましょう。

これには何通りか方法があって、例えば $S$ 全体が $23415$ だったときに、末端のノードが持つ値を $\lbrace 2, 3, 4, 1, 5\rbrace$ と持つ方法や、 $\lbrace 20000, 3000, 400, 10, 5\rbrace$ と持つ方法があります。どちらでも解けますが今回は後者で考えてみます。

末端のノードが持つ値を $\lbrace 20000, 3000, 400, 10, 5\rbrace$ のようにすれば、区間同士をマージする二項演算 op は単なる足し算で良いです。この data だけを記したセグメント木の全体構造は以下のようになります。

f:id:betrue12:20200927012610p:plain

次に lazy として持つ「操作を表す値」を考えますが、これは更新クエリで書き換える1桁の整数をそのまま持てば良いでしょう。値を上書きする更新クエリなので、冒頭で紹介した記事の「区間更新操作の恒等写像」に書いたように恒等写像 id と操作同士をマージする関数 composition を定義します。

問題は操作を data に対して行う関数 mapping です。ある区間内の数字を一様に上書き更新したときに、その区間が受け持つ値が何になるべきかは区間によって異なります。例えば下図において赤色で塗っている区間 $\lbrack 0, 2)$ は万の位から千の位までの合計を担当しているので、「区間 $\lbrack 0, 2)$ の数字を一様に $d$ に変更する」という操作によってこのノードが持つデータは $11000\times d$ になるべきです。

f:id:betrue12:20200927014224p:plain

この $11000$ というのは、「そのノードが持つ区間内の数字を一様に更新したときに、その数字に対していくつの係数を掛ければその区間が受け持つ値の和になるか」という値です。これも一緒に data として持ってしまうことにしましょう。末端ノードについては右から $1, 10, 100, ...$ という値を持たせておいて、マージする関数 op においてこっちも単に足し算をしてあげれば良いです。各ノードが持つ data は以下のような構造になります。