Codeforces 494C - Helping People

题意

有一个长度为 \(n\) 的数列 \(a\)，有 \(m\) 个 操作，每个操作是给 \(a[l_i,r_i]\) 中的数都加一，一个操作有 \(p_i\) 的概率执行（否则不执行）。一个性质是任意两个区间不相交或完全包含（可重叠）。问执行完所有操作后 \(a\) 中最大值的期望。

\(n\le 10^5,m\le 5000,a\le 10^9\) 。

分析

想象一下多个不相交或完全包含的区间，他们的结构其实是一棵树。外层为父亲，内层为儿子。

要计算的是最大值的期望，而这个最大值是由多个操作得到的，所以无法分别计算期望再合并。解决这个问题的方法是先算出概率，再得到期望。

到最后，一个区间 \([l,r]\) 的最大值只可能是 \([mx,mx+q]\) 中的数（\(mx\) 为原序列中这个区间的最大值）。那么那么我们可以用这个东西来 dp。

设 \(f[x][j]\) 表示 \(x\) 点子树中的操作结束后，\(x\) 点表示的这个区间的最大值小于等于 \(mx_x+j\) 的概率。这样设计是因为若是等于的话，计算的时候转移还是要求前缀和，相当于是小于等于了。若 \(x\) 这个操作不执行，那么从子树 \(v\) 转移，子树 \(v\) 需要让其最后的区间最大值小于等于 \(mx_x+j\) ；若执行，那么子树的需要让其区间最大值小于等于 \(mx_i+j-1\) 。因此有转移

代码

#include<bits/stdc++.h>

using namespace std;

const int maxq=5e3+5;

const int maxm=1e4+5;

const int maxn=1e5+1;

int n,a[maxn],m,M,mx;

inline void Max(int &x,int y) {x=max(x,y);}

struct Q {

	int l,r,mx;

	double p;

	inline bool operator < (const Q &b) const {return l!=b.l?l<b.l:r>b.r;}

} q[maxq];

namespace rmq {

	const int maxj=17;

	int f[maxn][maxj],bin[maxn];

	void build() {

		for (int i=2;i<=n;++i) bin[i]=bin[i>>1]+1;

		for (int i=1;i<=n;++i) f[i][0]=a[i];

		for (int j=1;j<maxj;++j) for (int i=1;i<=n;++i) {

			int x=i+(1<<(j-1));

			f[i][j]=f[i][j-1];

			if (x<=n && f[x][j-1]>f[i][j]) f[i][j]=f[x][j-1];

		}

	}

	inline int query(int l,int r) {

		int x=bin[r-l+1];

		return max(f[l][x],f[r-(1<<x)+1][x]);

	}

}

namespace tree {

	vector<int> g[maxq];

	double f[maxq][maxm];

	inline void add(int x,int y) {g[x].push_back(y);}

	void build() {

		sort(q+1,q+m+1);

		static int sta[maxq],top;

		q[sta[top=0]=0]=(Q){1,n,min(mx,m),0};

		for (int i=1;i<=m;++i) {

			Q &p=q[i];

			for (;top>0 && p.l>q[sta[top]].r;--top) add(sta[top-1],sta[top]);

			sta[++top]=i;

		}

		for (;top;--top) add(sta[top-1],sta[top]);

	}

	void dfs(int x) {

		if (g[x].empty()) {

			f[x][0]=1-q[x].p;

			for (int i=1;i<=M;++i) f[x][i]=1;

			return;

		}

		for (const int &v:g[x]) dfs(v);

		for (int j=0;j<=m;++j) {

			double fir=j?q[x].p:0,sec=1-q[x].p;

			for (const int &v:g[x]) {

				int the=q[x].mx-q[v].mx+j;

				fir*=f[v][the-1];

				sec*=f[v][the];

			}

			f[x][j]=fir+sec;

		}

		for (int j=m+1;j<=M;++j) f[x][j]=f[x][j-1];

	}

	double calc() {

		double ret=mx;

		for (int i=1;i<=m;++i) ret+=(f[0][i]-f[0][i-1])*i;

		return ret;

	}

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	scanf("%d%d",&n,&m),M=m<<1;

	for (int i=1;i<=n;++i) {

		scanf("%d",a+i);

		Max(mx,a[i]);

	}

	if (mx>m) for (int i=1;i<=n;++i) a[i]=max(0,a[i]+m-mx);

	rmq::build();

	for (int i=1;i<=m;++i) {

		scanf("%d%d%lf",&q[i].l,&q[i].r,&q[i].p);

		q[i].mx=rmq::query(q[i].l,q[i].r);

	}

	tree::build();

	tree::dfs(0);

	double ans=tree::calc();

	printf("%.10lf\n",ans);

	return 0;

}