CF494C:
题面翻译
有一个长为 $n$ 的数列，初始时为 $a_{1..n}$。
给你 $q$ 个操作，第 $i$ 个操作将 $[l_i,r_i]$ 内的数全部加一，有 $p_i$ 的概率被执行。保证区间不会交错，即：$\forall i,j\in[1,q],l_i\le r_i<l_j\le r_j$ 或 $l_i\le l_j\le r_j\le r_i$ 或 $l_j\le r_j<l_i\le r_i$ 或 $l_j\le l_i\le r_i\le r_j$ 。
求操作完成后数列的最大值的期望。
输入格式
第一行 $n,\,q\,(1\le n\le10^5,\,1\le q\le 5000)$。
第二行 $a_1,\,a_2,\,\cdots,\,a_n\,(0\le a_i\le10^9)$。
接下来 $q$ 行，每行 $l_i,\,r_i,\,p_i\,(1\le l_i\le r_i\le n,\,0\le p_i\le1)$。
输出格式
一个实数，表示答案，绝对/相对误差在 $10^{-6}$ 内算对。
Translated by ouuan.
题目描述
Malek is a rich man. He also is very generous. That’s why he decided to split his money between poor people. A charity institute knows $ n $ poor people numbered from $ 1 $ to $ n $ . The institute gave Malek $ q $ recommendations. A recommendation is a segment of people like $ [l,r] $ which means the institute recommended that Malek gives one dollar to every person whose number is in this segment.
However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation $ [a,b] $ and $ [c,d] $ one of the following conditions holds:
- The two segments are completely disjoint. More formally either $ a<=b<c<=d $ or $ c<=d<a<=b $
- One of the two segments are inside another. More formally either $ a<=c<=d<=b $ or $ c<=a<=b<=d $ .
The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help.
You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.
输入格式
Malek is a rich man. He also is very generous. That’s why he decided to split his money between poor people. A charity institute knows $ n $ poor people numbered from $ 1 $ to $ n $ . The institute gave Malek $ q $ recommendations. A recommendation is a segment of people like $ [l,r] $ which means the institute recommended that Malek gives one dollar to every person whose number is in this segment.
However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation $ [a,b] $ and $ [c,d] $ one of the following conditions holds:
- The two segments are completely disjoint. More formally either $ a<=b<c<=d $ or $ c<=d<a<=b $
- One of the two segments are inside another. More formally either $ a<=c<=d<=b $ or $ c<=a<=b<=d $ .
The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help.
You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.
输出格式
Output the sought value. Your answer will be considered correct if its absolute or relative error is less than $ 10^{-6} $ .
HDU5866
Problem Description
$ N $ lucky lancers are defending a tower. Each lancer occupies a position on the tower. Their leader, Lancer C¨2 Chulainn, a hero from the Ulster Cycle of Irish mythology, guards on the top of the tower. We can equalize the tower as a tree, each lancer has a supervisor. After several fierce battles, each lancer is wounded to a certain extent, the lancer with identity $ i $ took $ A_i $ arrows in his knee. This day, the lancers encounter the most powerful enemy ever – Gilgamesh. Using his Noble Phantasm, Gate of Babylon, Gilgamesh launched $ M $ attacks altogether toward the poor lancers. Each time, Gilgamesh chooses a lancer and attacks. Due to the lancers’ Protection from Arrows, this lancer has a probability to avoid this attack. However, if he failed to evade the attack, he and all his subordinates would take an arrow in the knee.
You are given the list of lancers Gilgamesh chose, we consider value $ S $ as the value of maximum number of arrows a lancers takes after Gilgamesh attacks.
Now C¨2 Chulainn would like to know the excepted value of $ S $.
Input
The input data will contain several cases(No more than $5$). Each case will begin with two numbers $ N $ and $ M $, the number of Lancers and the number of Gilgamesh’s attacks. Each of the next $ n - 1 $ lines includes two numbers $ u $ and $ v $, meaning that $ v $ is $ u $’s supervisor.
The next line have N numbers , and the ith number indicates the number of arrows which the ith lancer have had initially in his knee.
The next M line means the attacks of Gilgamesh, include a integer v and a real number p, indicating the v-th lancer will be choose , and he has a probability p that he can’t avoid this attack.
$ N \leq 100000, M \leq 3000 , A_i \leq 10000 , 0 \leq p \leq 1.0 , 1 \leq v \leq N $
Output
For each test case, print one line, the excepted value of $S$. The answer is round to $6$ decimal digits.
题意简述
给出一个 $N$ 个点的树(树以 $1$ 为根)，树上的每一个点有点权。
接下来进行 $M$ 次操作作用于 $M$ 个不同的点，每次操作有 $p_i$ 的概率使得这个点及子树内所有点点权 $+1$。
求树上点权最大值的期望。
乍一看两道题毫无相似之处。
但两道题其实是双倍经验。
CF494C 中有这样一句话：
保证区间不会交错。
区间不交错，意味着区间之间要么包含要么无交。
要么包含要么无交，这就是在 $ \stackrel{{ \text{ 明摆着 }}} { \small \textsf{暗示} } $ 这是一个树型结构。
包含的区间将被包含的区间视为父亲，$\Theta(n)$ （假如 $\Theta(n)$ 排序）就能把树建出来。
同样的，用 dfs 序可以将 HDU5866 的子树拍扁成区间。
HDU5866
首先要明确，期望的最大值不是最大值的期望。
如果直接算期望的话比较麻烦。
但众所周知，期望就是概率乘上值，又因为值域很小，于是可以求出每种值出现的概率，然后推期望。
首先，没用的点很多，只有被操作的 $m$ 个点是真的有用的。
于是就可以用 $m$ 个关键点和 $1$ 建虚树，每个点只保留其子树的最大值 $mx_i$。
void redfs(int p,int fa,int top){
if(p!=1&&q[p].size()){
v[top].push_back(p);
top=p;
dfn[p]=++tot;
}
mx[p]=a[p];
for(auto to:u[p]){
if(to==fa)continue;
redfs(to,p,top);
mx[p]=max(mx[p],mx[to]);
}
}
接下来可以愉快的树形 DP 求概率。
设 $f_{i,j}$ 表示以 $i$ 为根的子树中，最大值为 $j$ 的概率。
然而这样开有点浪费，因为一个子树的最大值至少为 $mx_i$ （一次也不加），至多也就是 $mx_i + m$ ($m$ 次全加上)。
于是可以设 $f_{i,j}$ 表示以 $i$ 为根的子树中，最大值比原来的最大值刚好大 $j$ 的概率（ $j$ 可能为负 ）。
这样子能做，但还是有点麻烦，要拆贡献。
于是我们再设 $f_{i,j}$ 表示以 $i$ 为根的子树中，最大值比原来的最大值至多大 $j$ 的概率（ $j$ 还是可能为负 ）。
可以发现，我们本质上就是做了个前缀和一样的东西，现在的 $f_{i,j} - f_{i,j-1}$就是原来的 $ f_{i,j} $。
但这样只需要将所有东西都加上就好了，没什么难推的地方。
设原来树上的最大值为 $MX$，以 $i$ 为根的子树构成的点集为 $T_i$。
如果以 $mx_i$ 一开始就大于 $MX + j$ ，那么 $f_{i,j} = 0$。
否则，对于对点 $i$ 的操作，设其发生概率为 $p_i$，则有 $p$ 的概率，原来最大值不大于 $j-1$ ，加上 $1$ 后不大于 $j$，有 $1 - p$ 的概率，原来最大值不大于 $j$ ，现在还是不大于 $j$。
由于我们先进优秀的状态设计，中间的各种情况都被囊括其中了。
最终得到 $f_{i,j} = (1 - p_i) \times \prod_{k \in T_i}f_{k,j} + p \times f_{p_i,j-1} $。
void dfs(int p){
for(int i=0;i<=m*2+1;i++){
if(mx[p]<=mx[1]+i-m-1)f[dfn[p]][i]=1;
else f[dfn[p]][i]=0;
}
for(auto to:v[p]){
dfs(to);
for(int i=0;i<=m*2+1;i++)
f[dfn[p]][i]*=f[dfn[to]][i];
}
for(auto t:q[p]){
for(int i=m*2+1;i;i--)
f[dfn[p]][i]=(1-t)*f[dfn[p]][i]+t*f[dfn[p]][i-1];
f[dfn[p]][0]=(1-t)*f[dfn[p]][0];
}
}
code
懒得写多测。
值得一提的是，将状态优化后，状态数量降到了 $\Theta(m^2)$ 个，也就是说，值域可以开回 1e9 了（笑。
时间复杂度是 $\Theta(n + m^2)$。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
using db=double;
const int N=1e5+5,M=3005;
int n,m,a[N];
vector<int>v[N],u[N];
vector<db>q[N];
int dfn[N],tot,mx[N];
void redfs(int p,int fa,int top){
if(p!=1&&q[p].size()){
v[top].push_back(p);
top=p;
dfn[p]=++tot;
}
mx[p]=a[p];
for(auto to:u[p]){
if(to==fa)continue;
redfs(to,p,top);
mx[p]=max(mx[p],mx[to]);
}
}
db f[M][M*2];
void dfs(int p){
for(int i=0;i<=m*2+1;i++){
if(mx[p]<=mx[1]+i-m-1)f[dfn[p]][i]=1;
else f[dfn[p]][i]=0;
}
for(auto to:v[p]){
dfs(to);
for(int i=0;i<=m*2+1;i++)
f[dfn[p]][i]*=f[dfn[to]][i];
}
for(auto t:q[p]){
for(int i=m*2+1;i;i--)
f[dfn[p]][i]=(1-t)*f[dfn[p]][i]+t*f[dfn[p]][i-1];
f[dfn[p]][0]=(1-t)*f[dfn[p]][0];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
u[x].push_back(y),u[y].push_back(x);
}
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int x;db p;
cin>>x>>p;
q[x].push_back(p);
}
tot=1,dfn[1]=1;
redfs(1,0,1);
dfs(1);
db ans=0;
for(int i=m+1;i<=m*2+1;i++)
ans+=(mx[1]+i-m-1)*(f[1][i]-f[1][i-1]);
printf("%.3lf\n",ans);
return 0;
}
//marisa
CF494C
如上所述，只要把区间转成虚树，这题就和 HDU5866 一模一样了。
一个小区别就是只有虚树没有原来的树推不出来子树最大值，所以要在建树前求一下RMQ。
时间复杂度是 $\Theta(n \log n + m^2)$，用一些 $O(1)$ RMQ 之类的科技或许可以做到 $\Theta(n + m^2)$。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using db=double;
const int N=1e5+5,M=5005,logN=20;
int n,m,a[N];
struct node{int l,r;db p;}s[M];
inline bool cmp(node x,node y){
if(x.l==y.l)return x.r>y.r;
else return x.l<y.l;
}
int st[N][logN],lg[N];
inline int query(int l,int r){
int k=lg[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int mx[N];
vector<int> v[N];
db f[M][M*2];
void dfs(int p){
for(int i=0;i<=m*2+1;i++){
if(mx[p]<=mx[1]+i-m-1)f[p][i]=1;
else f[p][i]=0;
}
for(auto to:v[p]){
dfs(to);
for(int i=0;i<=m*2+1;i++)
f[p][i]*=f[to][i];
}
db t=s[p].p;
for(int i=m*2+1;i;i--)
f[p][i]=(1-t)*f[p][i]+t*f[p][i-1];
f[p][0]=(1-t)*f[p][0];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int j=1;j<logN;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=m;i++)
cin>>s[i].l>>s[i].r>>s[i].p;
s[++m]=(node){1,n,0};
sort(s+1,s+1+m,cmp);
for(int i=1;i<=m;i++)
mx[i]=query(s[i].l,s[i].r);
for(int j=2;j<=m;j++)
for(int i=j-1;i;i--)
if(s[i].l<=s[j].l&&s[j].r<=s[i].r){
v[i].push_back(j);
break;
}
dfs(1);
db ans=0;
for(int i=m+1;i<=m*2+1;i++)
ans+=(mx[1]+i-m-1)*(f[1][i]-f[1][i-1]);
printf("%.9lf\n",ans);
return 0;
}
//marisa
