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);
}