https://www.luogu.com.cn/problem/CF494C
首先无交,先建树,然后上dp,三个优化
dp维护概率算期望
发现期望很难直接维护,直接维护某种值得概率,最后乘起来算期望
dp状态大小分析
发现这样子第二维会很大。但其最大值范围只在 [ m x , m x + q ] [mx,mx+q] [mx,mx+q] 内,dp状态很少
dp状态维护前缀和
我们发现这样子转移很难打。我们直接维护最大值<=x的概率,也就是前缀和。最后做一遍差分就行
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 5010
#define M 100010
//#define mo
struct asfsfasfdsaf {int l, r;
}b[N];
struct node {int x, y, id, op;
}c[N<<2];
int n, m, i, j, k, T;
int Log2[M], f[M][22], st[N], top, q;
int z[M], a[M];
double dp[N][N], p[N], ans;
vector<int>G[N]; bool cmp(node x, node y) {if(x.x==y.x) {if(x.op==y.op) {if(x.op==1) return x.y>y.y; else return x.y<y.y; }return x.op<y.op; }return x.x<y.x;
}int Mx(int l, int r) {int k=Log2[r-l+1]; return max(f[l][k], f[r-(1<<k)+1][k]);
}int re(int x) {if(x>q) return q; return x;
}void dfs(int x) {int i, j;
// printf(">> %d [%lld %lld] %lld\n", x, b[x].l, b[x].r, st[x]); for(int y : G[x]) dfs(y); for(int y : G[x]) {dp[x][0]*=dp[y][re(st[x]-st[y])]; //所有区间无+操作
// printf("%d %d %lf\n", y, re(st[x]-st[y]), dp[y][re(st[x]-st[y])]); }
// printf("%d [%d %d]\n", x, b[x].l, b[x].r);
// printf("dp[%lld][%lld]=%lf\n", x, 0ll, dp[x][0]); for(i=1; i<=q; ++i) {double p1=1, p2=1; for(int y : G[x]) {p1*=dp[y][re(i+st[x]-st[y]-1)]; p2*=dp[y][re(i+st[x]-st[y])]; }dp[x][i]=p[x]*p1+(1-p[x])*p2;
// printf("dp[%lld][%lld]=%lf %lf\n", x, i, dp[x][i], p1); }
// printf("\n");
}signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// T=read();
// while(T--) {
//
// }n=read(); q=read(); for(i=1; i<=n; ++i) a[i]=read(), f[i][0]=a[i]; for(k=1; k<=20; ++k) for(i=1, j=1+(1<<k-1); i+(1<<k)-1<=n; ++i, ++j) {f[i][k]=max(f[i][k-1], f[j][k-1]); }for(i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1; for(i=1, k=0; i<=q; ++i) {b[i].l=read(); b[i].r=read(); scanf("%lf", &p[i]); st[i]=Mx(b[i].l, b[i].r); c[++k]={b[i].l, b[i].r, i, 1}; c[++k]={b[i].r, b[i].l, i, 2}; }st[q+1]=Mx(1, n); b[q+1].l=1; b[q+1].r=n; sort(c+1, c+2*q+1, cmp); z[top=0]=q+1; for(i=1; i<=2*q; ++i) {
// printf("%lld\n", c[i].id); if(c[i].op==2) --top; else G[z[top]].pb(c[i].id), z[++top]=c[i].id; }for(i=1; i<=q+1; ++i) dp[i][0]=1-p[i]; //确实小于等于
// printf("%lld\n", q+1); dfs(q+1); ans=(double)st[q+1]*dp[q+1][0]; for(i=1; i<=q; ++i) {
// printf("%lf %lf\n", (double)(st[q+1]+i), (dp[q+1][i]-dp[q+1][i-1])); ans+=(double)(st[q+1]+i)*(dp[q+1][i]-dp[q+1][i-1]); }printf("%.8lf", ans); return 0;
}