Codeforces #282 div 1 C Helping People 题解_html/css_WEB-ITnose

CF 282 C Helping People Problem Solution

[Original question] is no longer posted.

[Bullshit] I haven’t blogged for a long time. (I won’t tell you that I wrote it offline) Then came the water experience.

[Source brief description] CF 282 C

[Original title brief description] There are N (10^5) people, each person has initial money. Then give M (5000) operations L, R, P. Each time, it means that these people L~R have a probability P (0<=P<=1) to give each of them one yuan. Find the expectation of the maximum amount of money for everyone in the end.

[Brief description of the algorithm] First, these operations are established into a tree structure (you can learn from the line segment tree). Node i represents the range Li~Ri, its father must contain it, and it also contains all its subtrees. For convenience, establish an invalid node with L=1, R=N, P=0 as the root.

It is observed that the range of M is small. We use f[i][j] to represent the expectation of the amount of money added <=j within the range represented by node i (note the original The amount of money can be calculated using RMQ). As for why it is <=, because the prefix sum will be used later?? Anyway, when f is calculated, the prefix sum is added. Then to node i, we open an array tmp[j] to represent the expectation that the shadows in all subtrees are at most (note that it is still a prefix sum property) with j elements added.

Then tmp[j]= ∏f[son][mx[i] j-mx[son]];

mx[o] is the maximum amount of money in the original interval o.

(The prefix and properties of f are used here)

Note that after completing the calculation, do a step of tmp[j]-=tmp[j-1] to cancel the prefix and properties.

Then our task is to find all f values ​​of i.

Then ans[i][j]=ans[i][j-1] tmp[j-1]*p[i] tmp[j]*(1-p[i]);

ans[i][j-1]: prefix sum

tmp[j-1]*p[i]: get the maximum plus j-1 from the subtree, and currently also add

tmp[j]*(1-p[i]): Get the maximum addition j from the subtree, and there is currently no addition

After calculating all f[i][j], For the newly added point K, the final ans satisfies

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

[*Essence obtained]A tree algorithm similar to divide and conquer.

[Code]

#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]实质是前缀和性质)     //tmp[k-1]*p[i]:由子树中得最大加k-1，且当前也加    //tmp[k]*(1-p[i]): 由子树中得最大加k,且当前不加  }   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);}