封印宝石 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100000 + 100;
struct Node {
    int a, idx;
};

bool operator<(const Node &a, const Node &b) {
    return a.a == b.a ? a.idx < b.idx : a.a > b.a;
}

int n, k, idx;
int ans[maxn], a[maxn];
bool vis[maxn];
set<Node> st;
set<Node>::iterator it;

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= n; ++i) {
        idx = max(idx, i);
        while (idx <= n && idx - i <= k) {
            if (!vis[idx]) {
                st.insert({a[idx], idx});
            }
            ++idx;
        }
        while (idx - 1 >= i && idx - 1 - i > k) {
            st.erase({a[idx - 1], idx - 1});
            --idx;
        }
        if (!st.empty()) {
            if (ans[i - 1] == -1 || ans[i - 1] != st.begin()->a) {
                it = st.begin();
            } else {
                it = st.upper_bound({ans[i - 1], n});
            }
            if (it != st.end()) {
                ans[i] = it->a;
                vis[it->idx] = true;
                k -= it->idx - i;
                st.erase(it);
            }
        }
        st.erase({a[i], i});
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}