题面
小C桌上有$n(n \leq 10^6)$杯水排成一行,第$i$杯水中有$a_i$单位体积的水. 他会选择一个区间$[l, r]$, 并拿一个初始为空的杯子(杯子的容积无限大),他可以重复无限次以下操作: • 选定任意一杯水$i$, $i \in [l, r]$. • 使i和它拿着的杯子里的水的体积变为它们的平均值. 小C希望进行若干操作后最大化杯子里的水的体积,设$g(l, r)$为这个最大值.你需要求: \(\sum{i=1}^n\sum{j=i}^n\frac{g(i,j)}{n^2}\)
思路
显然地，对于每个区间可以应用基于交换的贪心证明由小到大地依次取物品最优。
想到按位置计算贡献之后，应该怎么做？
注意到eps = 1e-2，而取的物品的贡献乘上了 $2^{-i}$ ，当$i$很小的时候，贡献就可以忽略不计！
统计贡献的一般思路是什么？对于每个位置的元素，综合它在所有可能的区间里面的贡献之和。对于本题，我们就应该统计出某个位置$i$左侧和右侧大于等于它的元素有多少个，记做$t_l,t_r$。特别地，如果$t_l,t_l$大于常数$T$，那么由于eps，此处的贡献就可以忽略不计！
设题目中的数列为${a_n}$，记$l_i$为从$p$位置向左第$i$个大于等于$a_p$的元素的位置，$r_i$为从$p$位置向右第$i$个大于等于$a_p$的元素的位置，为了方便，$l_0 = r_0 = p$ .
于是有该位置的贡献：
\[\begin{aligned}sum_p &= a_p \times \sum_{i = 1}^T \sum_{j = 1}^T (l_{i-1} - l_i) \times (r_j- r_{j-1}) \times \frac{1}{2^{i + j - 1}} \\ &= 2a_p (\sum_{i=1}^T \frac{l_{i-1} - l_i}{2^i}) (\sum_{j=1}^T \frac{r_j - r_{j-1}}{2^j}) \end{aligned}\]再来考虑如何实现的问题：由于$2^{-50} \approx 8.9 \times 10^{-16}$，取$T=50$即可。
最后考虑如何查找两侧大于它的元素：可以先排序后拉链，从小到大地计算贡献值，算完某个的贡献后，显然它不会比接下来要算的数大，因此删掉即可。对于相等的元素，仔细思考会发现也得删掉，因为二者共同产生的贡献最后也只能保留一个！
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6, MAXT = 50;
int N, A[MAXN+10], Rk[MAXN+10], LLnk[MAXN+10], RLnk[MAXN+10];
template<typename T>
inline void readint(T& x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
x=f*r;
}
bool cmp(int lhs, int rhs) {
return A[lhs] == A[rhs] ? lhs < rhs : A[lhs] < A[rhs] ;
}
void Init() {
readint(N);
for(int i=1; i<=N; i++) readint(A[i]);
for(int i=1; i<=N; i++) Rk[i] = i;
sort(Rk+1, Rk+N+1, cmp);
for(int i=0; i<=N+1; i++) LLnk[i] = i-1, RLnk[i] = i+1;
}
void Work() {
double Ans=0, SumL, SumR, t;
for(int i=1; i<=N; i++) {
int l = LLnk[Rk[i]], r = RLnk[Rk[i]];
SumL = SumR = 0;
t = .5;
for(int j=1; l>=0 && j<=MAXT; j++, l = LLnk[l], t/=2) {
SumL += (RLnk[l] - l) * t;
}
t = .5;
for(int j=1; r<=N+1 && j<=MAXT; j++, r = RLnk[r], t/=2) {
SumR += (r - LLnk[r]) * t;
}
Ans += SumL * SumR * A[Rk[i]] * 2;
RLnk[LLnk[Rk[i]]] = RLnk[Rk[i]];
LLnk[RLnk[Rk[i]]] = LLnk[Rk[i]];
}
printf("%.12lf", Ans / N / N);
}
int main() {
freopen("drink.in", "r", stdin);
freopen("drink.out", "w", stdout);
Init(); Work();
return 0;
}
UPD: 感觉对标算理解还是有一点偏差。过几天再看看。
