題目描述：
給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
西月弦 閱讀(330)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告