题目描述：
给1,000,000个数，大小不超过10^9。询问1,000,000次，长度为k的区间最小值的期望。
算法分析：
看到询问次数我们就知道要离线处理出所有的长度k区间的最小值之和了。
用栈线性扫出每个点i，右边最近的小于它的位置r，和左边最近的不大与它的位置l。
那么在区间(l,r)内，最小值一定是i的值。
我们发现，对于k < min(l,r) ，每个区间k都有k种可能。
对于k<max(l,r) , k>= min(l,r)，每个区间k有min(l,r)种可能。
对于k>max(l,r) ，每个区间k有 ***种可能（也是线性的）。
发现用直接维护答案，线段树是办不到的。于是这道题的亮点来了。
我们可以维护一个数组ans[i]， 让ans[1] +... + ans[i]是答案。
这样给ans数组建立线段树，就可以做了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int N = (int) 1e6 + 10;
int num[N], Q[N],M,n,m;
ll sum[N<<2], ans[N];
void add(int l, int r, ll c){
// cout<<l<<" "<<r<<" "<<c<<endl;
for(l+= M-1, r += M+1;l^r^1; l>>=1, r>>=1) {
if(r&1) sum[r^1] += c;
if(~l&1) sum[l^1] += c;
}
}
ll find(int pos){
ll a = 0;
while(pos) a += sum[pos], pos >>=1;
return a;
}
int main(){
while(~scanf("%d",&n)){
num[0]= num[n+1] = -1;
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=30;i;i--) if((1<<i) >= n+4) M = 1<<i;
for(int i=0;i<M+M;i++) sum[i] = 0;
int tp = 1;
Q[0] = 0;
for(int i=1;i<=n+1;i++) {
while(num[Q[tp-1]] > num[i]) {
tp--;
int l = Q[tp] - Q[tp-1] ;
int r = i - Q[tp] ;
int v = num[Q[tp]];
int mn = min(l,r);
int mx = max(l,r);
// cout<<"i: "<<Q[tp]<<" "<<mn<<" "<<mx<<endl;
// up
add(1,mn,v);
add(mx+1,mn+mx,-v);
}
Q[tp++] = i;
}
int m,v;
scanf("%d",&m);
for(int i=1;i<=n;i++) {
ans[i] = ans[i-1] + find(i+M);
}
for(int i=0;i<m;i++) {
scanf("%d",&v);
printf("%.10lf\n",1.0*ans[v]/(n-v+1));
}
}
return 0;
}
posted on 2012-08-05 19:57
西月弦 阅读(327)
评论(0) 编辑 收藏 引用 所属分类:
解题报告