【原題】不貼了。

【廢話】好久沒(méi)寫博客了。（我不會(huì)告訴你我是離線寫的）于是來(lái)水經(jīng)驗(yàn)來(lái)了。

【來(lái)源簡(jiǎn)述】CF 282 C

【原題簡(jiǎn)述】有N（10^5）個(gè)人，每個(gè)人有初始的錢。再給出M（5000）個(gè)操作L,R,P。每次表示L~R這些人有幾率P（0<=P<=1）給他們每人一元。求最后所有人錢數(shù)最大值的期望。

【算法簡(jiǎn)述】首先把這些操作建立出樹結(jié)構(gòu)（可以借鑒線段樹）。節(jié)點(diǎn)i表示范圍Li~Ri，它的父親一定包含它，它也包含它的所有子樹。為了方便，建立一個(gè)L=1,R=N,P=0的無(wú)效節(jié)點(diǎn)作為根。

觀察到M的范圍小，我們用f[i][j]表示在節(jié)點(diǎn)i表示的范圍內(nèi)，加的錢數(shù)<=j的期望（注意原先的錢數(shù)可以用RMQ計(jì)算出）。至于為什么是<=，因?yàn)楹竺嬉玫角熬Y和??反正f算的時(shí)候再前綴和一下。那么到節(jié)點(diǎn)i，我們開一數(shù)組tmp[j]表示所有子樹中影的最多（注意還是前綴和性質(zhì)）加了j元的期望。

那么tmp[j]= ∏f[son][mx[i]+j-mx[son]];

mx[o]是原先區(qū)間o的最大錢數(shù)。

（這里就用到了f的前綴和性質(zhì)了）

注意到求完后做一步tmp[j]-=tmp[j-1]，取消前綴和性質(zhì)。

然后我們的任務(wù)是求出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，且當(dāng)前也加

tmp[j]*(1-p[i]):由子樹中得最大加j,且當(dāng)前不加

求完了所有的f[i][j]后，我們對(duì)于新加的點(diǎn)K，最后的ans滿足

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

【*精華所得】類似于分治的樹形算法。

【代碼】

#include#include#include#define N 100005#define M 5005using namespace std;struct arr{int l,r;double p;}a[M];int f[N][18],mx[N],used[N],n,i,j,T,m,k;double ans[M][M],tmp[M],ANS;inline int ask(int x,int y){ int len=(int)log2(y-x+1); return max(f[x][len],f[y-(1<=a[i].l&&a[j].r<=a[i].r&&!used[j]) { used[j]=1; for (k=0;k<=m;k++) if (mx[i]+k-mx[j]<=m) tmp[k]*=ans[j][mx[i]+k-mx[j]]; } for (k=m;k;k--) tmp[k]-=tmp[k-1]; ans[i][0]=(1-a[i].p)*tmp[0]; for (k=1;k<=m;k++) ans[i][k]=ans[i][k-1]+tmp[k-1]*a[i].p+tmp[k]*(1-a[i].p); //ans[i][k-1]:加上k-1的期望(ans[i]實(shí)質(zhì)是前綴和性質(zhì)) //tmp[k-1]*p[i]:由子樹中得最大加k-1，且當(dāng)前也加 //tmp[k]*(1-p[i]): 由子樹中得最大加k,且當(dāng)前不加 } ANS=ans[m][0]*mx[m]; for (i=1;i<=m;i++) ANS+=(ans[m][i]-ans[m][i-1])*(mx[m]+i); printf("%.10lf",ANS);}

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com