Blog

题目

Atcoder

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 500010, INF = 1e9;
int n, k, P[N], st[N], ans[N];
struct NODE { int l, r, mx; } tr[N << 2];
void pushup(int u) {
    int l = tr[u << 1].mx, r = tr[u << 1 | 1].mx;
    if (P[l] > P[r]) tr[u].mx = l; 
    else tr[u].mx = r;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l >= r) return tr[u].mx = l, void(0);
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
int query(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return 0;
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx;
    int a = query(u << 1, l, r), b = query(u << 1 | 1, l, r);
    return P[a] > P[b] ? a : b;
}
void modify(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].mx = 0, void(0);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) modify(u << 1, x);
    if (x > mid) modify(u << 1 | 1, x);
    pushup(u);
}
priority_queue<int> Q;
void check(int i) {
    if (st[i]) return;
    if (query(1, i - k + 1, i + k - 1) == i) 
        Q.push(i), st[i] = true;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> P[i];
    P[0] = -INF, build(1, 1, n);
    for (int i = 1; i <= n; i++) check(i);
    for (int i = n; i >= 1; i--) {
        int t = Q.top(), pos; Q.pop();
        ans[t] = i, modify(1, t);
        int l = query(1, t - k + 1, t - 1);
        int r = query(1, t + 1, t + k - 1);
        if (l) check(l);
        if (r) check(r);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}