help!!!为何70分

P1440 求m区间内的最小值

Him_shu @ 2024-04-19 21:07:52

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
#define inf 1e14
#define mod 1000000009
int n,m;
int dp[N][20];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>dp[i][0];
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
    cout<<"0\n";
    for(int b=1;b<n;b++){
        int a=max(b-m+1,1ll);
        int k=log2(b-a+1);
        cout<<min(dp[a][k],dp[b-(1<<k)+1][k])<<"\n";
    }
    return 0;
}

为何70分


by cj180202 @ 2024-04-19 21:17:19

空间炸了咩


by cj180202 @ 2024-04-19 21:17:52

@Him_shu 本题卡ST,使用空间 O(n) 的单调队列即可


by Him_shu @ 2024-04-20 14:37:15

谢谢 大佬


|