dp维护概率算期望+dp状态大小分析+dp状态维护前缀和：CF494C

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133343917

https://www.luogu.com.cn/problem/CF494C

首先无交，先建树，然后上dp，三个优化

dp维护概率算期望

发现期望很难直接维护，直接维护某种值得概率，最后乘起来算期望

dp状态大小分析

发现这样子第二维会很大。但其最大值范围只在 [mx,mx+q][mx,mx+q] 内，dp状态很少

dp状态维护前缀和

我们发现这样子转移很难打。我们直接维护最大值<=x的概率，也就是前缀和。最后做一遍差分就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#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;
}