解説
解説
レートの更新式を変形すると、
Ri=2019Ri−1+20Pi
となります。そこで、第 i 回のコンテストに対応するアフィン変換
fi(x)=2019x+20Pi
を考え、その合成を遅延セグメント木で管理します。
区間情報のマージ
各区間について、合成関数 f(x)=ax+b を表す組 (a,b) を管理します。
左右の区間の情報をそれぞれ (aL,bL),(aR,bR) とすると、
fR(fL(x))=aRaLx+aRbL+bR
より、マージ後の情報は
(aRaL, aRbL+bR)
となります。単位元は (1,0) です。
区間加算
区間内のすべてのパフォーマンスと初期レートに v を加えると、最終的なレートも v 増加します。
したがって、更新後の合成関数は
f′(x)=f(x−v)+v=ax+b+(1−a)v
となるため、作用を
(a,b)↦(a,b+(1−a)v)
とすればよいです。作用素の合成は加算、単位元は 0 です。
クエリの処理
区間 [ki,N] に xi を加算した後、区間 [li+1,ri] の情報 (a,b) と、対応する葉から Pli を取得します。
求める答えは aPli+b です。
以上より、時間計算量 O(N+QlogN)、空間計算量 O(N) でこの問題を解くことができました。