贪心+线段树

$首先此题要求得到字典序最大的序列，\\ 那么贪心思路就是在满足体力的情况下，将魔力值最高的宝石放在前面的盒子\\ 设体力值为k，枚举当前盒子下标为i，\\ 则需要求[i, i + k]范围内宝石的最大值，\\ 但是题中要求连续的两个盒子中的宝石魔力值不能相同\\ 此时我们还要求[i, i + k]中的次大值(最大值与次大值不能相同)\\ 但由于体力用完会消耗，窗口不固定，所以不能用滑动窗口解$

$如果我们暴力求的话就是O(nk), k的范围为10^9铁超时\\$

$如果我们事先将所有的宝石的值排好序，然后从大到小判断是否满足条件的话\\ 由于排序需要动态，每次用完一个宝石需要删掉再排，\\ 可以用<set>来排序和删除(erase), \\ <set>底层实现时红黑树，插入和删除的时间复杂度是O(nlogn) $
该打暴力打暴力，线段树一遍过很难呀 :(

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 100010;

int n, k;
set<PII> dom;
int box[N];

int main(){
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i ++){
        int t;
        scanf("%d", &t);
        dom.insert({-t, i});//保证所有宝石都是魔力按最大到小排，索引按从小到大排
    }

    for (int i = 1; i <= n; i ++){
        int val = -1, index = i;
        for (auto u = dom.begin(); u != dom.end(); u ++){
            int tv = - u->x, ti = u->y;
            if (ti >= i && ti - i <= k && box[i - 1] != tv){
                val = tv, index = ti;
                break;
            } 
        }

        box[i] = val;
        k = k - (index - i);
        dom.erase({-val, index});
    }

    for (int i = 1; i <= n; i ++){
        printf("%d ", box[i]);
    }
    return 0;
}

$最后只能用线段树来维护区间[i, i + k]的最大值和次大值了,\\ 为了减去对应体力还需要记录最大值和次大值对应的下标$

$时间复杂度，线段的查询和修改都是logn$

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 100010;

int n, k;
int a[N], b[N];
bool st[N];

struct Node{
    int l, r;
    int v, nv;
    int vi, nvi;
}tr[4 * N];

inline bool cmp(PII a, PII b){
    if (a.x == b.x){
        return a.y < b.y;
    }
    return a.x > b.x;
}

inline void pushup(Node& u, Node& l, Node& r){
    static PII tmp[4]; //卡的非常死，必须用数组，用vector就超时
    tmp[0] = {l.v, l.vi};
    tmp[1] = {l.nv, l.nvi};
    tmp[2] = {r.v, r.vi};
    tmp[3] = {r.nv, r.nvi};
    sort(tmp, tmp + 4, cmp);

    u.v = tmp[0].x, u.vi = tmp[0].y;
    for (int i = 1; i < 4; i ++){
        if (tmp[i].x != tmp[i - 1].x){
            u.nv = tmp[i].x, u.nvi = tmp[i].y;
            break;
        }
    }
}

inline void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

inline void build(int u, int l, int r){
    tr[u] = {l, r};
    if (l == r) {
        tr[u].v = a[r]; tr[u].vi = r; // nv = 0, nvi = 0;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

inline Node query(int u, int l, int r){
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    Node res = {0, 0, 0, 0, 0};
    //求max允许重叠
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid){
        Node t = query(u << 1 | 1, l, r);
        pushup(res, res, t);
    }
    return res;
}

inline void modify(int u, int x){
    if (tr[u].l == x && tr[u].r == x){
        tr[u].v = 0, tr[u].vi = 0;
        tr[u].nv = 0, tr[u].nvi = 0;
        return;
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x);
        else modify(u << 1 | 1, x);
        pushup(u);
    }
}

int main(){
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, 1, n);

    for (int i = 1; i <= n; i ++){
        Node t = query(1, i, min(i + k, n));
        int val = -1, index = -1;
        if (b[i - 1] == t.v && t.nv != 0) {
            b[i] = t.nv;
            modify(1, t.nvi);
            k = max(0, k - (t.nvi - i));
        }
        if (b[i - 1] != t.v && t.v != 0){
            b[i] = t.v;
            modify(1, t.vi);
            k = max(0, k - (t.vi - i));
        }
    }

    for (int i = 1; i <= n; i ++){
        printf("%d ", b[i] ? b[i] : -1);
    }
    return 0;
}