yukicoder No.885 アマリクエリ

• 問題
• AC (sparse table)
• AC (平衡二分木)

$A_i := A_i \% X_1, A_i := A_i \% X_2, ...$とmodを取っていくとき、値が変化するのは$A_i \ge X_k$であるような$k$についてだけである。また値が変化するときは必ず半分以下になるので、変化する回数は初期値について高々$\log_2 A_i$である。そこで、各$A_i$について、$X_{k_0} \le A_i$であるような最小の$k_0 \in [1, Q]$を求めて$A_i := A_i \% X_{k_0}$とし、$X_{k_1} \le A_i$であるよな最小の$k_1 \in [k_0, Q]$を求めて$A_i := A_i \% X_{k_1}$とし……を繰り返して、各クエリで総和がどれだけ減るかを記録する。この操作は例えばSparse Table上の二分探索でできる。

$A := \max_i A_i$とするとき、計算量は${\mathcal O}(N(\log A \log Q + \log N))$。

---

コンテスト中は上の方針でやったのだが、よく考えると、順序付き集合に$A$全体を入れておいてクエリごとにシミュレーションすれば十分だった。

先読みできる設定だとまずそれを利用したくなるけど、良し悪しありそう。