前置知识
解法
观察到区间只有相离或包含关系，类似线段树的管辖区间，考虑将其构成树形关系。为方便代码书写，将原来的森林构成一棵树，即增加一个区间 \(l_{q+1}=1,r_{q+1}=n,p_{q+1}=0\)。
由于对于一个区间 \([l,r]\) 的最大值在经历任意次操作后，一定有 \(\max\limits_{k=l}^{r} \{ a_{k} \} \le \max\limits_{k=l}^{r} \{ a_{k}' \} \le \max\limits_{k=l}^{r} \{ a_{k} \}+q\)，故可以据此优化空间。设 \(f_{x,i}\) 表示第 \(x\) 个节点对应的区间的最大值 \(\le \max\limits_{k=x_{l}}^{x_{r}} \{ a_{k} \}+i\) 的概率，状态转移方程为 \(\begin{cases} f_{x,i}=(1-p_{x}) \times \prod\limits_{y \in Son(x)}f_{y,\min(q+1,\max\limits_{k=x_{l}}^{x_{r}} \{ a_{k} \}+i-\max\limits_{k=y_{l}}^{y_{r}} \{ a_{k} \})} & i=0 \\ f_{x,i}=p_{x} \times \prod\limits_{y \in Son(x)}f_{y,\min(q+1,\max\limits_{k=x_{l}}^{x_{r}} \{ a_{k} \}+i-\max\limits_{k=y_{l}}^{y_{r}} \{ a_{k} \}-1)}+(1-p_{x}) \times \prod\limits_{y \in Son(x)}f_{y,\min(q+1,\max\limits_{k=x_{l}}^{x_{r}} \{ a_{k} \}+i-\max\limits_{k=y_{l}}^{y_{r}} \{ a_{k} \})} & i \ne 0 \end{cases}\)。
假设区间按照左端点升序，右端点降序的方式排序。最终，有 \(f_{1,0} \times \max\limits_{k=1}^{n} \{ a_{k} \}+\sum\limits_{i=1}^{q+1}(f_{1,i}-f_{1,i-1}) \times (i+ \max\limits_{k=1}^{n} \{ a_{k} \})\) 即为所求。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct edge
{
int nxt,to;
}e[5010];
struct node
{
int l,r,maxx;
double p;
}b[5010];
int head[5010],a[100010],fmaxx[100010][20],cnt=0;
double f[5010][5010];
bool cmp(node a,node b)
{
return (a.l==b.l)?(a.r>b.r):(a.l<b.l);
}
void init(int n)
{
for(int j=1;j<=log2(n);j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
{
fmaxx[i][j]=max(fmaxx[i][j-1],fmaxx[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r)
{
int t=log2(r-l+1);
return max(fmaxx[l][t],fmaxx[r-(1<<t)+1][t]);
}
void add(int u,int v)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int x,int q)
{
double sum1,sum2=1;
for(int i=head[x];i!=0;i=e[i].nxt)
{
dfs(e[i].to,q);
sum2*=f[e[i].to][min(q,b[x].maxx+0-b[e[i].to].maxx)];
}
f[x][0]=(1-b[x].p)*sum2;
for(int i=1;i<=q;i++)
{
sum1=sum2=1;
for(int j=head[x];j!=0;j=e[j].nxt)
{
sum1*=f[e[j].to][min(q,b[x].maxx+i-b[e[j].to].maxx-1)];
sum2*=f[e[j].to][min(q,b[x].maxx+i-b[e[j].to].maxx)];
}
f[x][i]=b[x].p*sum1+(1-b[x].p)*sum2;
}
}
int main()
{
int n,q,i,j;
double ans=0;
cin>>n>>q;
for(i=1;i<=n;i++)
{
cin>>a[i];
fmaxx[i][0]=a[i];
}
init(n);
for(i=1;i<=q;i++)
{
cin>>b[i].l>>b[i].r>>b[i].p;
b[i].maxx=query(b[i].l,b[i].r);
}
q++;
b[q].l=1;
b[q].r=n;
b[q].p=0;
b[q].maxx=query(1,n);
sort(b+1,b+1+q,cmp);
for(i=1;i<=q;i++)
{
for(j=i-1;j>=1;j--)
{
if(b[j].l<=b[i].l&&b[i].r<=b[j].r)
{
add(j,i);
break;
}
}
}
dfs(1,q);
for(i=0;i<=q;i++)
{
ans+=(f[1][i]-(i==0?0:f[1][i-1]))*(i+b[1].maxx);
}
printf("%.9lf\n",ans);
return 0;
}