题解 CF212D 【Cutting a Fence】
青鸟_Blue_Bird
2020-06-25 00:16:43
#### [AC传送门！](https://www.luogu.com.cn/problem/CF212D)
看题目，首先肯定是要先想想我们应该用什么处理方法。1e6的询问题，我们肯定是不能在线处理的，因此先确定：
#### 先尽可能预处理出最终答案，然后输出
于是乎，开始动手吧：
根据题目中f的定义，我们要找到许多区间中的最小值。那么，假设我们的一个数 $a_x$ (1≤x≤n)，如何找到一个区间使得其最小值为$a_x$呢？
并不难，只要我们找到了它最左边的第一个小于它的数$a_l$,以及它右边第一个小于等于它的数$a_r$，那么对于区间[l+1, r-1],其最小值就是$a_x$。
即： 对于一个数$a_x$,其作为最小值得区间为 [l + 1 , r - 1],（其中$a_l$ < $a_x$ 且 $a_r$ < $a_x$, l,r均为区间 [l , x]与 [x , r]中的最小值)
那么，我们设变量 L 为左区间 [l + 1, x] 的长度， R 为右区间 [x, r - 1] 的长度。
我们~~强制~~假设L ≤ R
### 那么，对情况进行分类讨论：
为了方便，我们把“有x个区间符合要求” 暂时定义为 “有x个区间满足有$min_x$ = $a_x$"
1、如果 k $\in$ [1 , L] 那么就会有 k 个区间符合要求
2、如果 k $\in$ [L + 1, R] ,那么会有 L 个区间符合要求。
3、如果 k $\in$ [R + 1, L + R - 1] 那么会有(L + R - K)个区间满足要求。
那么，对于一个数对应的贡献 $sum_x$ ，对应有：
1、$sum_x$ = $sum_x$ + k * $a_x$
2、$sum_x$ = $sum_x$ + L * $a_x$
3、$sum_x$ = $sum_x$ + $a_x$ * (L + R) - k * $a_x$
观察以上~~柿子~~，不难发现，他们都是： $a_x$ * k + B 的格式。也就是说，除了变量K，剩下的都是定值。
#### 那么，我们为什么不快速求出每一个~~柿子~~的 B 呢？
于是，我们改变一下，以 K 参考系:
设$S_1$ = $\sum_{}a_x$(满足上述条件) -> 即为上文所述的所要乘上k的 $a_x$ 的和。
$S_2$ = $\sum_{}^{}n$($n$为任意实数） -> 即为上文所述的B
对于一个数K，$ans_k$ = ($S_1$ * k + $S_2$) / (n - k + 1)
具体的例子，我觉得大家可以参考[PinkCloud大佬的博客](https://www.luogu.com.cn/blog/LuckyCloud/solution-cf212d)：
那么，我们如何实现快速求和呢？ 对$S_1$和$S_2$数组分别进行差分即可。
具体实现还是看代码吧：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
inline ll read(){
ll x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-')s = -1;
c = getchar();
}
while(isdigit(c)){
x = x * 10 + (c ^ '0');
c = getchar();
}
return x * s;
}
ll n, m, r[N], l[N], a[N];
ll s1[N], s2[N];
double ans[N];
void search(){
for(int i = n; i; i--){ /*向右找到第一个小于等于这个数的位置*/
if(a[i + 1] <= a[i]) r[i] = i + 1;
else
for(int j = r[i + 1]; j <= n + 1; j = r[j]) /*一直向右跑*/
if(a[j] <= a[i]){
r[i] = j;
break;
}
}
for(int i = 1;i <= n; i++){ /*同上，向左找*/
if(a[i - 1] < a[i]) l[i] = i - 1;
else
for(int j = l[i - 1]; j >= 0; j = l[j])
if(a[j] < a[i]) {
l[i] = j;
break;
}
}
for(int i = 1;i <= n; i++){ /*换算成距离 L 和 R*/
l[i] = i - l[i];
r[i] = r[i] - i;
}
return ;
}
void prepare(){ /*进行差分以及预处理答案*/
for(int i = 1;i <= n; i++){
int x = l[i], y = r[i];
if(x > y) swap(x, y); /*保持 L < S*/
s1[1] += a[i];
s1[x + 1] -= a[i];
s2[x + 1] += a[i] * x;
s1[y + 1] -= a[i];
s2[y + 1] += a[i] * y;
s1[x + y] += a[i];
s2[x + y] -= a[i] * (x + y);
}
ll num1 = 0, num2 = 0;
for(int i = 1;i <= n; i++){
num1 += s1[i], num2 += s2[i];
ans[i] = ((num1 * i + num2) * 1.00) / ((n - i + 1) * 1.00); /*预处理出所有答案*/
}
return ;
}
int main(){
n = read();
for(int i = 1;i <= n; i++)
a[i] = read();
a[n + 1] = (ll)(-(1 << 50));/*两端插入极小值，避免下一步越界或者出现错误*/
a[0] = (ll)(-(1 << 50));
search(); /*先搜索距离*/
prepare(); /*然后处理答案*/
m = read();
while(m--){
ll k = read();
printf("%.9lf\n", ans[k]);
}
return 0;
}
```