给定 \(n\) 个数 \(a_{1,2...n}\)，每次随机操作一个区间，即将这个区间 \([l,r]\) 的数变成这个区间的 \(\max\)
操作 \(Q\) 次，输出最后每个元素的权值的期望。
\(n,Q\le 400\)
期望的套路是差分贡献，当然直接计数也可以这样处理，所以不妨枚举 \(x\)，设 \(f_{l,r,k}\) 表示当前操作了 \(k\) 次，区间 \([l,r]\) 均小于 \(x\)，同时 \(a_{l-1},a_{r+1}\) 均大于等于 \(x\) 的方案数。（当然小于等于的位置设为 \(0\)，其他位置设为 \(1\)），那么答案即为 \(\max - \sum f_{...}\times (w_x-w_{x-1})\)
然后考虑转移：
其中 \(q(l,r)\) 表示无用操作的数量。
考虑前缀和数组 \(S_1(l,r,k),S_2(l,r,k)\)，分别维护一下即可，复杂度为 \(\mathcal O(n^3q)\)
可以考虑将初始值设为 \(w_x-w_{x-1}\)，这样就不需要将答案乘以 \(w_x\) 了。
考虑优化到 \(\mathcal O(n^3)\)，不难发现对于不同的 \(x\)，转移只有初值不同，所以对每个区间预处理初值和即可。
注意到 \([l,r]\) 的初值即 \(\min(a_{l-1},a_{r+1})-\max(a_{l,l+1...r})\)，于是复杂度 \(\mathcal O(n^2q)\)
原文：https://www.cnblogs.com/Soulist/p/13675016.html