求Hack
查看原帖
求Hack
977730
CBQZZYJ楼主2024/8/16 16:44
#include <bits/stdc++.h>
#define mod 998244353
#define int long long
#define N 1000005
#define V 21
using namespace std;
int n, a[N], m, b[N];
int st[N][V];
void build() {
    for (int i = 0; i <= n; i++) {
        st[0][i] = a[i];
    }
    for (int i = 1; i < V; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
    }
}
int ask(int l, int r) {
    int lg = log2(r - l + 1);
    return max(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build();
    for (int i = 1; i <= n - m; i++) {
        a[i] = ask(i, i + m);
    }
    n = n - m;
    int ans = LONG_LONG_MAX;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, a[i]);
    }
    cout << ans;
}

ST表

2024/8/16 16:44
加载中...