CF494C Helping People 题解

CF494C Helping People 题解

题意

$ $ 给出长为 (n (1le nle 10^5)) 的数列 ({a_i} (1le a_ile 10^9))。共 (m (1le mle 5 imes 10^3)) 次操作，第 (i) 次操作有 (p_i) 的概率将 ([l_i,r_i]) 内所有数加 (1) ，求所有操作完成后的数列最大值的期望。保证所有操作区间不相交。（即仅会相离或包含）

---

题解

(~~~~) 很好的题，用学长的话来说可以让人回归期望的本质。（笑

(~~~~) 要先知道 (operatorname{E}(max{a_i}) ot = max{operatorname{E}(a_i)}) （不然就是线段树板子了）

(~~~~) 如果我们从期望DP入手，很难找到一个合适的方法去DP。这个时候不妨想想：期望 (=) 概率 ( imes) 值，而这道题中值是很好求的，因此不妨直接DP概率。

(~~~~) 再看操作区间不相交的条件，这个条件使得区间之间构成树形的关系，所有操作就是一个森林了。因此不难想到增加一个操作 (m+1) ： (l_{m+1}=1,r_{m+1}=n,p_{m+1}=0) 这样既不会对答案有影响，又让所有区间形成了一棵树。

(~~~~) 得到这个性质后不难想到树形 DP ，定义DP状态 (dp_{u,i}) 表示在 (u) 节点对应的区间内最大值 (le i) 的概率。由于某个区间的最大值 (maxn) 在任何操作后一定在 ([maxn,maxn+m]) 之间，因此仅在 (i in [maxn,maxn+m]) 时我们才需要这个值。因此更改定义： (dp_{u,i}) 表示在 (u) 节点对应的区间内最大值 (le i+maxn_u) 的概率。此时 (i) 一定满足 (0 le i le m) ，时空都得到了优化。

(~~~~) 由此可以得到一个转移：

[Large dp_{u,i}=p_u imes prod _{vin operatorname{son(u)}} dp_{v,i-maxn_v+maxn_u-1} + (1-p_u) imes prod_{vin operatorname{son(x)}} dp_{v,i-maxn_v+maxn_u} ]

(~~~~) 而当 (i=0) 时仅取上式加号的后面部分即可。

(~~~~) 若令我们新增的区间为 (1) ，则最后答案即为：

[Large sum_{i=0}^m (dp_{1,i}-dp_{1,i-1}) imes (i+maxn_1) ]

(~~~~) 求取最大值时可以用 ST 表。

(~~~~) 总的时间复杂度为 (mathcal{O(n log n+m^2)}).

(~~~~) 另外注意千万不能在CF将 C++11 和 long double 并用。

代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> G[5005];
struct node{
	int l,r,maxn;
	double p;
	node(){}
	node(int L,int R,double P,int Maxn){l=L,r=R,p=P,maxn=Maxn;}
}op[5005];
double dp[5005][5005];
int n,m,lg[100005],arr[100005],f[100005][105];
void inti()
{
	for(int i=1;i<=n;i++) f[i][0]=arr[i];
	int t=lg[n]+1;
	for(int j=1;j<t;j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r)
{
	int k=lg[r-l+1];
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
void read(int &x)
{
	int f=1;x=0;char c=getchar();
	while(!('0'<=c&&c<='9')){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}
	x*=f;
}
inline bool cmp(node x,node y)
{
	return x.l^y.l?x.l<y.l:x.r>y.r;
}
void DP(int u)
{
	int v;
	for(int i=0;i<(int)G[u].size();i++) DP(G[u][i]);
	dp[u][0]=1-op[u].p;
	for(int i=0;i<(int)G[u].size();i++) v=G[u][i],dp[u][0]*=dp[v][op[u].maxn-op[v].maxn];
	for(int i=1;i<=m;i++)
	{
		double p1=1,p2=1;
		for(int j=0;j<(int)G[u].size();j++)
		{
			v=G[u][j];
			p1*=dp[v][min(i-op[v].maxn+op[u].maxn-1,m)];
			p2*=dp[v][min(i-op[v].maxn+op[u].maxn,m)];
		}
		dp[u][i]=op[u].p*p1+(1-op[u].p)*p2;
	}	
	
}
int main() {
	int maxn=-1;
	read(n);read(m);
	for(int i=1;i<=n;i++)
	{
		read(arr[i]);
		maxn=max(maxn,arr[i]);
		if(i!=1) lg[i]=lg[i>>1]+1;	
	}
	inti();
	for(int i=1;i<=m;i++)
	{
		read(op[i].l);read(op[i].r);
		scanf("%lf",&op[i].p);
		op[i].maxn=query(op[i].l,op[i].r);
	}
	op[++m]=node(1,n,0.0,query(1,n));
	sort(op+1,op+1+m,cmp);
	for(int i=2;i<=m;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(op[j].l<=op[i].l&&op[i].r<=op[j].r)
			{
				G[j].push_back(i);
				break;
			}
		}
	}
	DP(1);
	long double ans=0;
	for(int i=0;i<=m;i++) ans+=((dp[1][i]-(!i?0:dp[1][i-1]))*(i+maxn));
	printf("%.9Lf",ans);
	return 0;
}