问题描述
小v家有一条护栏，由n个木板组成。第i个木板的高度是a[i]。现在小镇上流行给护栏画矩形，所以小v也要在自家的护栏上画。若要在区间[x,x+k-1]这个区间画一个宽度为k的矩形（1<=x<=n-k+1）,为了美观，高度一定是这个区间里高度最低的木板。现在小v有m个心中理想的宽度，第i个为ki，(ki与kj之间可能一样，1<=i<=n,1<=j<=n)他想知道对于每个ki，求矩形高度的期望。
输入格式
第一行一个整数n，表示木板的数目。第2行有n个数，第i个数ai表示第个木板的高度。第3行一个整数m。第4行有m个数，表示小v心中理想的第i个宽度ki
输出格式
输出m行实数，第i行表示宽度为ki的 矩形高度的期望，只要你的答案和正确答案的差的绝对值小于10的-9次方，你的答案将被视为正确。
样例输入
3
3 2 1
4
1 2 3 1
3 2 1
4
1 2 3 1
样例输出
2.000000000000000
1.500000000000000
1.000000000000000
2.000000000000000
1.500000000000000
1.000000000000000
2.000000000000000
数据规模和约定
1 ≤ n ≤ 106
1 ≤ ai ≤ 109
1 ≤ m ≤ 106
1 ≤ ki ≤ n
1 ≤ ai ≤ 109
1 ≤ m ≤ 106
1 ≤ ki ≤ n
长度N的序列，所有位置到权值不大于他的位置距离和是nlogn级的……这个很显然。
然后我们高度从小到大来求有哪些长度的区间高度是这个。
我们需要知道他左方和右方距离他最近的在他之前计算过的点在哪。
这个线段树可以logn解决……我写的二分加树状数组log^2n的……
然后枚举起点，这个枚举的范围在距离近的那边，然后发现是对一段区间加同一个数……而且最后问，那就等价于对前缀和操作。
之前证明了距离和是nlogn级的，所以这个操作的复杂度就均摊为nlogn。
然后最后O(1)回答询问就行了。
算法瓶颈在于线段树或者二分加树状数组部分……线段树的话是nlogn的……二分加树状数组nlog^2n……二分加树状数组常数比较小还给了8s是可以过的。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,i,j,k,l,r,mid,L,R,len,x;
int where[1000011],a[1000011],dl[1000011],tree[1000011];
long long s[1000011];
bool cmp(int x,int y)
{
return a[x]<a[y];
}
int lowbit(int x)
{
return x-(x&(x-1));
}
void ins(int x)
{
while (x<=n)
{
tree[x]++;
x+=lowbit(x);
}
}
int qsum(int x)
{
int ans=0;
while (x)
{
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
cin >> n;
for (i=1;i<=n;i++) cin >> a[i],dl[i]=i;
sort(dl+1,dl+n+1,cmp);
for (i=1;i<=n;i++)
{
l=1,r=dl[i];
while (l!=r)
{
mid=(l+r)/2;
if (qsum(dl[i])-qsum(mid-1)==0) r=mid;
else l=mid+1;
}
L=l;
l=dl[i],r=n;
while (l!=r)
{
mid=l+r-(l+r)/2;
if (qsum(mid)-qsum(dl[i]-1)==0) l=mid;
else r=mid-1;
}
R=r;
ins(dl[i]);
if (dl[i]-L<R-dl[i]) x=dl[i]-L+1,len=R-dl[i];
else x=R-dl[i]+1,len=dl[i]-L;
for (j=1;j<=x;j++)
s[j]+=a[dl[i]],s[j+len+1]-=a[dl[i]];
}
for (i=1;i<=n;i++)
s[i]+=s[i-1];
cin >> m;
for (i=1;i<=m;i++)
{
cin >> k;
printf("%.11f\n",s[k]/(double)(n-k+1));
}
return 0;
}