P1440 求m区间内的最小值

题目描述

一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$ 。

输入格式

第一行两个整数，分别表示 $n$ ， $m$ 。

第二行， $n$ 个正整数，为所给定的数列 $a_{i}$ 。

$1 \leq m \leq n \leq 2 \times 10^{6}$ ， $1 \leq a_{i} \leq 3 \times 10^{7}$ 。

输出格式

$n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_{i}$ 之前 $m$ 个数的最小值。

Solution

线段树/DP/RMQ/单调队列

(RMQ：Range Minimum Query)

线段树求最小值(开 $O 2$ 才能过)

#define lc u<<1
#define rc u<<1|1
int a[2000010];
struct Tree { //线段树
    ll l, r, min;
}tr[8000010];
void pushup(ll u) { //上传
    tr[u].min = min(tr[lc].min, tr[rc].min);
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l]};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
ll querymin(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;
    ll m = tr[u].l + tr[u].r >> 1;
    ll ans = INTMAX_MAX;
    if (l <= m) ans = min(ans, querymin(lc, l, r));
    if (r > m) ans = min(ans, querymin(rc, l, r));
    return ans;
}
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build(1, 1, n);
    cout << "0\n";
    for (int i = 2;i <= n;i++) {
        int l = i - m, r = i - 1;
        if (!l)l = 1;
        cout << querymin(1, l, r) << '\n';
    }
}

单调队列：(待更 $\dots$ )