【问题描述】
小 v 家有一条栅栏,由 n 个木板顺序组成,第 i 个木板的高度是 Ai。现
在小镇上流行在栅栏上画矩形,所以小 v 也要在自家的栅栏上画。若要在区间
[x,x+k-1]这个区间画一个宽度为 k 的矩形(1≤x≤n-k+1),为了美观,高度一
定是这个区间里高度最低的木板。现在小 v 心中有 m 个理想的宽度,第 i 个为
Ki,(Ki 与 Kj 之间可能一样)。他想知道对于每个 Ki,其矩形高度的期望。
【输入格式】
第一行一个整数 n,表示木板的数目。
第二行有 n 个正整数,第 i 个数表示第 i 个木板的高度。
第三行一个整数 m,表示理想宽度的数目。
第四行有 m 个正整数,第 i 个数表示小 v 心中理想的第 i 个宽度 Ki。
【输出格式】
输出 m 行实数,第 i 行表示宽度为 Ki 的矩形高度的期望,只要你的答案和
正确答案的差的绝对值小于 1e-6,你的答案将被视为正确。
【输入样例】
3
3 2 1
4
1 2 3 1
【输出样例】
2.000000000000000
1.500000000000000
1.000000000000000
2.000000000000000
【数据范围】
对于 30%的数据,n≤20;m≤20;
对于 40%的数据,n≤2000;m≤2000;
对于 70%的数据,n≤100000;m≤100000;
对于 100%的数据,n≤1000000;m≤1000000;1≤Ai≤10 9 ;1≤Ki≤n;
输入较大,C++选手请使用读入优化。
%%%YZD大佬，考场怒切此题
本题要用到把差分数组差分和单调栈的技巧
0 x j i
|————|—————|—————|——————
假设我们维护一个单调递增的栈，当前点为i,j=q[tail],x=q[tail-1]
我们为了方便，写为[i,i]*[i,n]=s[i]
意思是以[i,i]为左端点，[i,n]为右端点的所有区间最小值为s[i]
如果h[i]<h[j],那么说明，之前我们认为的[x+1,j]*[i,n]=s[j]是错误的，我们要减去这些情况
再加上[x+1,j]*[i,n]=s[i]的情况
弹出j，执行单调栈操作
直到h[i]>h[j]，在加入[i,i]*[i,n]=s[i]的情况
为什么不要减去[j+1,i-1]*[i,n]？因为我们在读到i之前，[j+1,i-1]已经被处理完了
现在问题只有：怎样增加删除情况
令f[i]为长度为i的所有区间最小值的总和
我们来看一下[1,2]*[3,5]=s[i]的情况
长为2：2～3 f[2]+=s[i];
长为3：1～3，2～4 f[3]+=2*s[i];
长为4：1～4，2～5 f[4]+=2*s[i]
长为5：1～5 f[5]+=1*s[i]
我们发现，系数根据区间长呈勾函数
1 2 2 1
差分一次
1 1 0 -1 -1 0
二次差分
1 0 -1 -1 0 1
为什么要二次差分？
1 2 3 4 5 5 4 3 2 1
差分一次：1 1 1 1 1 0 -1 -1 -1 -1 -1
涉及了线段树区间操作，显然超时
但若再差分一次：1 0 0 0 0 -1 -1 0 0 0 0 1
就只要修改4个点
把二次差分拓展到[x+1,j]*[i,n]
最短的区间长是i-j+1，f[i-j+1]+=s[i]
最长的是区间长是n-x，f[n-x+2]+=s[i]
f[i-k+1]-=s[i]
f[n-k+2]-=s[i]
因为还要减去s[j]，所以将s[i]变成s[i]-s[j]就行
对于[i,i]×[i,n]=s[i]的系数
1 1 1 1 1 1 1(n-i+1) 0 0
差分：1 0 0 0 0 0 0 0 0 -1 0
再差分：1 -1 0 0 0 0 0 0 0 -1 1
就等价于：f[1]+=s[i],f[2]-=s[i],f[n-i+2]-=s[i],f[n-i+3]+=s[i]
得到最后的数组只要求两次前缀和就行了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
double f[];
int q[],tail,i,s[],n,m;
int gi()
{
char ch=getchar();
while (ch<''||ch>'') ch=getchar();
int x=;
while (ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x;
} int main()
{int i,k;
freopen("fence.in","r",stdin);
freopen("fence.out","w",stdout);
cin>>n;
for (i=;i<=n;i++)
{
s[i]=gi();
while (tail&&s[q[tail]]>s[i])
{
int j=q[tail],k=q[tail-];
f[i-j+]+=s[i]-s[j];
f[n-k+]+=s[i]-s[j];
f[n-j+]+=s[j]-s[i];
f[i-k+]+=s[j]-s[i];
tail--;
}
tail++;
q[tail]=i;
f[]+=s[i];f[]-=s[i];
f[n-i+]+=s[i];f[n-i+]-=s[i];
}
for (i=;i<=n;i++)
f[i]+=f[i-];
for (i=;i<=n;i++)
f[i]+=f[i-];
cin>>m;
for (i=;i<=m;i++)
{
k=gi();
printf("%.15lf\n",f[k]/(double)(n-k+));
}
}