题目意思很简洁明了: 总成本不超过 k的情况下,通过若干次操作,能够得到的字典序最大的序列是什么。
那么一个贪心的想法是将较大的数字尽可能的替换到前面来：
比如[1,1,1,4,1,5],我们希望将所有元素替换为5,变为[5,5,5,5,5,5],但是有k的限制条件
如果k = 0,那么最优是[1,1,1,4,1,5]
如果k = 1,那么最优是[1,1,4,4,1,5]
如果k = 2,那么最优是[1,4,4,4,1,5]
如果k = 3,那么最优是[4,4,4,4,1,5]
如果k = 4,那么最优是[4,4,4,4,5,5]
如果k = 5,那么最优是[5,5,5,5,5,5]
嗯....注意k = 4的情况最优是[4,4,4,4,5,5],而不是[1,5,5,5,5,5].原因是求字典序最大的序列,那么我们一定是首先看能不能替换第一个数变成更大的数字,然后看第二个数能不能替换更大的数字.....一直到最后一个数字或者k = 0
具体的做法是:
一开始判断第一个位置: 左边界 L = 1, 有边界 R = min(n, L + k), 然后在[L, R]中找到最大的数字X,并求出X在[L, R]中最左边的一个位置Pos, 那么我们此时就可以将[L, Pos]区间中所有的数字替换为X了, 成本为Pos - L, 所以 k -= (Pos - L)。这样做的目的是一定保证了第一个位置尽可能的最大,一定是最优解,顺便将[L,Pos]的值都替换了
还需要考虑后面能否继续替换的问题，具体看代码 
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int N = 2e5 + 10;
const int inf = -1e10;

struct Node{
    int l, r;
    int cov, Max;//cov表示的是区间是否要覆盖,如果cov = inf说明不需要覆盖
                 //Max表示区间的最大值
}tr[4 * N];
int n, k, a[N];

void push_up(int u){
    tr[u].Max = max(tr[u << 1].Max, tr[u << 1 | 1].Max);
}

void push_down(int u){
    if(tr[u].cov != inf){
        tr[u << 1].Max = tr[u].cov;
        tr[u << 1].cov = tr[u].cov;
        tr[u << 1 | 1].Max = tr[u].cov;
        tr[u << 1 | 1].cov = tr[u].cov;
        tr[u].cov = inf;
    }
}
void build(int u, int l, int r){
    if(l == r) tr[u] = {l, r, inf, a[l]};
    else{
        tr[u] = {l, r, inf, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

int query(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].Max;
    push_down(u);
    int ans = inf;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) ans = max(ans, query(u << 1, l, r));
    if(r > mid) ans = max(ans, query(u << 1 | 1, l, r));
    return ans;
}
//找到[l, r]中最左边等于x的位置
int find(int u, int l, int r, int x){
    if(tr[u].l > r || tr[u].r < l || tr[u].Max < x) return -1;
    if(tr[u].l == tr[u].r) return tr[u].l;
    push_down(u);
    int ans = -1;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) ans = find(u << 1, l, r, x);
    if(r > mid && ans == -1) ans = find(u << 1 | 1, l, r, x);
    return ans;
}

void modify(int u, int l, int r, int v){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].cov = v;
        tr[u].Max = v;
        return ;
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(u << 1, l, r, v);
    if(r > mid) modify(u << 1 | 1, l, r, v);
    push_up(u);
}
void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
    
    for(int i = 1; i <= n; ){
        int l = i, r = min(n, i + k);//[l, r]是查找区间
        int x = query(1, l, r);//x是[l, r]中的最大值
        int pos = find(1, l, r, x);//pos就是[l, r]中最左边等于x的位置
        k -= (pos - l);//替换的区间为[l, pos],所以代价pos - l;
        //当k > 0表示我还能操作
        //pos < n表示我还可以继续判断后面的数
        while(k > 0 && pos < n){
            int l1 = pos + 1, r1 = min(n, l1 + k);//后面要判断的区间
            int x1 = query(1, l1, r1);
            if(x > x1){
                pos ++;
                k --;
            }
            else break;
        }
        modify(1, l, pos, x);
        i = pos + 1;
    }
    for(int i = 1; i <= n; i ++) cout << query(1, i, i) << " ";
    cout << endl;
    return ;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}