2019年9月14日土曜日

yukicoder No.885 アマリクエリ

yukicoder No.885 アマリクエリ

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

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


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

オフラインでよい設定だとまずオフラインの方針を調べてみたくなるのだけど、良し悪しありそう。