外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

R - NyanCoder Munchkin Contest

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 500 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

解説

レートの更新式を変形すると、

Ri=1920Ri−1+Pi20R_i=\frac{19}{20}R_{i-1}+\frac{P_i}{20}

となります。そこで、第 ii 回のコンテストに対応するアフィン変換

fi(x)=1920x+Pi20f_i(x)=\frac{19}{20}x+\frac{P_i}{20}

を考え、その合成を遅延セグメント木で管理します。

区間情報のマージ

各区間について、合成関数 f(x)=ax+bf(x)=ax+b を表す組 (a,b)(a,b) を管理します。

左右の区間の情報をそれぞれ (aL,bL),(aR,bR)(a_L,b_L),(a_R,b_R) とすると、

fR(fL(x))=aRaLx+aRbL+bRf_R(f_L(x))=a_Ra_Lx+a_Rb_L+b_R

より、マージ後の情報は

(aRaL, aRbL+bR)(a_Ra_L,\ a_Rb_L+b_R)

となります。単位元は (1,0)(1,0) です。

区間加算

区間内のすべてのパフォーマンスと初期レートに vv を加えると、最終的なレートも vv 増加します。

したがって、更新後の合成関数は

f′(x)=f(x−v)+v=ax+b+(1−a)vf'(x)=f(x-v)+v=ax+b+(1-a)v

となるため、作用を

(a,b)↦(a,b+(1−a)v)(a,b)\mapsto(a,b+(1-a)v)

とすればよいです。作用素の合成は加算、単位元は 00 です。

クエリの処理

区間 [ki,N][k_i,N] に xix_i を加算した後、区間 [li+1,ri][l_i+1,r_i] の情報 (a,b)(a,b) と、対応する葉から PliP_{l_i} を取得します。

求める答えは aPli+baP_{l_i}+b です。

以上より、時間計算量 O(N+Qlog⁡N)O(N+Q\log N)、空間計算量 O(N)O(N) でこの問題を解くことができました。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。