算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:

   给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 西月弦 阅读(322) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理