倍增的ST 然后全RE 尴尬

P1440 求m区间内的最小值

war1111 @ 2017-07-17 16:47:40

#include<iostream>
#include<cmath>
using namespace std;
int f[200001][20];
int a[200001];
int n,m;
void st()
{
    for(int i=0;i<n;i++)
    f[i][0]=a[i];
    double N=(double)n;
    int l=(int)(log(N)/log(2.0));
    for(int j=1;j<=l;j++)
      for(int i=0;i<n;i++)
        {
            if(i+(1<<j)-1<n)
            {
                f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            }
        }
}
int R(int l,int r)
{
    double aaaa=(double)(r-l+1);
    int L=(int)(log(aaaa)/log(2.0));
    return min(f[l][L],f[r-(1<<(L))+1][L]);
}
int main()
{
    cin>>n;cin>>m;
    for(int i=0;i<n;i++)
    cin>>a[i];
    st();
    for(int i=0;i<n;i++)
    {
        if(i<=m)
        {
            cout<<R(0,i-1)<<endl;
        }
        else 
        {
            cout<<R(i-m,i-1)<<endl;
        }
    }
    return 0;
}

|