Codeforces #282 div 1 C 人々を助ける 题解_html/css_WEB-ITnose

CF 282 C Helping People 質問解決

【元の質問】は投稿されなくなりました。

【でたらめ】長い間ブログを書いていませんでした。 （オフラインで書いたことは言いません）そして水体験です。

【出典の簡単な説明】CF 282 C

【元の質問の簡単な説明】N (10^5) 人がいて、各人が初期資金を持っています。次に、M (5000) に L、R、P の演算を与えます。毎回、これらの人々 L ～ R がそれぞれ 1 元を与える確率 P (0

【アルゴリズムの簡単な説明】 まず、これらの演算のツリー構造を確立します (線分ツリーから学ぶことができます)。ノード i は範囲 Li~Ri を表し、その父親にはそれが含まれている必要があり、そのすべてのサブツリーも含まれています。便宜上、L=1、R=N、P=0 をルートとして無効なノードを作成します。

M の範囲が小さいことに注目してください。f[i][j] を使用して、ノード i で表される範囲内に追加される金額 の期待値を表します (元の金額はお金は RMQ を使用して計算できます)。なぜ<=なのかというと、接頭辞の合計が後で使われるから?? とにかく、fを計算するときに接頭辞の合計が加算されます。次に、ノード i に到達したら、配列 tmp[j] を開き、j 個の要素を追加して、すべてのサブツリーのシャドウが最大 (依然として接頭辞合計プロパティであることに注意してください) を持つという期待を表します。

すると、 tmp[j]= ∏f[son][mx[i]+j-mx[son]];

mx[o] は元の区間 o における最大金額です。

(f のプレフィックスとプロパティはここで使用されます)

計算が完了したら、tmp[j]-=tmp[j-1] のステップを実行してプレフィックスとプロパティをキャンセルすることに注意してください。

次に、私たちのタスクは、i のすべての f 値を見つけることです。

すると、 ans[i][j]=ans[i][j-1]+tmp[j-1]*p[i]+tmp[j]*(1-p[i]);

ans [i][j-1]: プレフィックス合計

tmp[j-1]*p[i]: サブツリーから最大加算 j-1 を取得し、現在は

tmp[j]*(1- p [i]): サブツリーから最大の加算 j を取得します。現時点では加算はありません

すべての f[i][j] を計算した後、新しく追加された点 K について、最終的な ans は次を満たします

ANS=ans [ m][0]*mx[m]+Σ (ans[m][i]-ans[m][i-1])*(mx[m]+i);

【*

エッセンス】 分割統治に似たツリーアルゴリズム。

【コード】

れー