题目本身很简单，但是可以加强。
P10668 列队春游
题目大意：
给你一个 \(n\) 个数，你可以等概率随机一种排列 \(h\)。
定义 \(\mathrm{pre}_i\) 为最大的 \(j\lt i\) 满足 \(h_j\ge h_i\)（如果不存在，规定为 \(0\)）。
求出 \(\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)\) 的期望值，保留两位小数输出。
题目思路：
原版：
首先，对于原本的题目的数据强度：\(1\leq n\leq 300\)，\(1\leq h_i\leq 1000\)，我们可以直接枚举第 \(i\) 个数在 \(j\)，上一个比它大的数在 \(k\)，那它对期望的贡献就是：
\[\frac{1}{n} \times \frac{A_{num\{ h_x < h_i \}}^{j-k}}{A_{n-1}^{j-k}} \times \frac{num\{ h_x \ge h_i \}}{n-(j-k+1)} \times (j-k) \]特别的，当 \(k=0\) 即 \(j\) 前面没有大于 \(h_j\) 的数，则答案为：
\[\frac{1}{n} \times \frac{A_{num\{ h_x < h_i \}}^j}{A_{n-1}^j} \times j \]直接预处理大于某一个值的 \(h_i\) 的数量。复杂度最多 \(O(n^3)\)。
加强版：
我们考虑，如果数据变成了 \(1\leq n\leq 1e5\)，\(1\leq h_i\leq 1e7\) 之后我们怎么求解。
首先，\(O(n^3)\) 是肯定不行了，要变换思路。
我们反过来考虑，对于某个 \(h_i\)，只有小于 \(h_i\) 的数可以产生贡献，假设数量为 \(sum\)。
那么我们先把这 \(sum\) 都拿出来，剩下的数都是大于等于 \(h_i\) 的，之后再将这 \(sum\) 个数不停插入。这时，这 \(n-sum\) 个数产生了 \(n-sum+1\) 个间隙，发现插入的 \(sum\) 个数只有插在 \(i\) 之前的空隙才会产生贡献，贡献为 \(1\)，所以总共会给期望产生 \(\frac{sum}{n-sum+1} \times 1\) 的贡献。
有个小优化，就是大小相同的数可以统一计算。
然后这道题就结束了，具体看代码。
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int rt=0; char g=getchar();
while(g<'0'||g>'9') g=getchar();
while(g>='0'&&g<='9') rt=(rt<<3)+(rt<<1)+g-'0',g=getchar();
return rt;
}
int n,a[1000006],sum,num;
int ck[10000005];
double ans;
int main()
{
ans=n=read();
for(int i=1;i<=n;i++) ck[a[i]=read()]++;
sort(a+1,a+1+n); a[0]=a[1]-1;
for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) a[++num]=a[i];
for(int i=1;i<=num;i++)
ans+=1.0*sum*ck[a[i]]/(n-sum+1),sum+=ck[a[i]];
printf("%.2lf",ans);
return 0;
}