2023河南萌新联赛第（六）场：河南理工大学-F 爱睡大觉的小C

2023河南萌新联赛第（六）场：河南理工大学-F 爱睡大觉的小C

https://ac.nowcoder.com/acm/contest/63602/F

题意

新学期的概率论课上，小C正在睡大觉，然而概率论老师的讲课声音还是传到了小C的梦里…
原本小C正在梦中享受打败小Y的胜利，突然小C面前出现了一个长度为$n(1\le n\le 2\times 10^5)$的数组$a_1,a_2,a_3,...a_n(1\le a_i\le 10^7)$ ,然后概率论老师的声音飘入了他的梦境：“这第$k$个较大的数的期望是…”,于是小C便想求出对于所有长度大于等于$k(1\le k\le 100)$的连续子区间中第$k$大的数的期望是多少。请你帮小C计算出来。
文本解释：
连续子区间：对于一个数组，它的连续子区间可以由删掉头和尾的0个或多个数字得到，例如$a=[1,4,2,6,5]$，则集合$[1,4,2],[4,2,6]$都是集合$a$的连续子区间，而集合$[1,2,6]$则不是，因为跳过$a_2=4$，不连续了
第$k$大的数：一个数组中有最大的数,次大的数,…,第个$k$大的数。 例如：$a=[[114514,1557,2333,666,369]$显然第一大的数是$114514]$，第二大的数是$2333$。
期望：在概率论和统计学中，数学期望（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和

解题思路

看题面，$1\le k\le 100$尤其引人注目，必有大用。可以发现小于其的数对其是否为区间第$k$大没有影响，我们可以使用链表，按照数值将 { a } \{a\} {a}排序，从小到大枚举，每处理完一个数就将它从链表中删除，对于某个数$x$，大于其的数都在链表中，而小于其的数都被删去。在其中找到最前的包含$x$使$x$为第$k$大的$l$，让$l$通过链表直到$x$，在此过程中求取各个合法的期望值，可以达到$O(nk)$的复杂度。注意处理边界情况。
##代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct link{int lf,rf;
}b[N];
struct node{int x,id;
}c[N];
int a[N],n,k;
long long dp[N];
bool cmp(node a,node b){return a.x<b.x;
}
void Delete(int x){b[b[x].lf].rf=b[x].rf;b[b[x].rf].lf=b[x].lf;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];c[i].x=a[i];c[i].id=i;b[i].lf=i-1,b[i].rf=i+1;}b[n+1].rf=n+1;sort(c+1,c+n+1,cmp);for(int i=1;i<=n;i++){int x=c[i].id;int l=x;int j;for(j=1;j<k&&b[l].lf!=0;j++)l=b[l].lf;int L=b[l].lf;int r=x;for(;j<k&&b[r].rf!=n+1;j++)r=b[r].rf;if(j<k){Delete(x);continue;}int R=b[r].rf;while(L!=x&&r!=n+1){dp[x]+=1ll*(l-L)*(R-r);l=L,L=b[L].lf;r=R,R=b[R].rf;}Delete(x);}long long sum=0;for(int i=1;i<=n;i++)sum+=dp[i];double ans=0;for(int i=1;i<=n;i++)ans+=1ll*a[i]*dp[i]*1.0/sum;printf("%.2lf",ans);
}