Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 278 D問題 All Assign Point Add

AtCoder ABC278 ABC D問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる. 次の $Q$ 個のクエリを順に処理せよ.

Type 1 : $A$ の $N$ 個の全ての要素を $x_q$ に置き換える.
Type 2 : $A_{i_q}$ に $x_q$ を加える.
Type 3 : $A_{i_q}$ を出力する.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$
$1 \leq i_q \leq N$
$0 \leq x_q \leq 10^9$
Type 3 のクエリが存在する.

解法

次のように各クエリを処理することによって高速化できる. なお, $D$ を辞書とし, ${\rm base}$ は最初 $-1$ で処理する.

Type 1 : ${\rm base} \gets x_q$ とし, $D$ の内容を全て破棄する.
Type 2 : $D_{i_q}$ に $x_q$ を加算する.
Type 3 : ${\rm base}=-1$ ならば, $A_{i_q}+D_{i_q}$ を出力, そうでなければ ${\rm base}+D_{i_q}$ を出力する.

なお, 最初に与えられる $A$ について, $Q$ 個のクエリの前に, 次のような $(N+1)$ 個のクエリがあったとみなすことによって Type 3 における場合分けをなくすことが出来る.

Type 1: $x_q=0$
Type 2: $i_q=1, x_q=A_1$
$\vdots$
Type 2: $i_q=N, x_q=A_N$