编辑代码

#include <iostream>
#include <algorithm>

#define int long long 
using namespace std;

const int N = 5e5 + 50;

int n, k;
int a[N], tree[4*N], left_idx[N], right_idx[N], left_fa[N], right_fa[N];

// 建立线段树
void build(int rt, int l, int r) {
    if (l == r) {
        tree[rt] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt * 2, l, mid);
    build(rt * 2 + 1, mid + 1, r);
    tree[rt] = min(tree[rt * 2], tree[rt * 2 + 1]);
}

// 查询区间最小值及其下标
pair<int, int> query(int rt, int l, int r) {
    if (l == r ){
        return make_pair(tree[rt], l);
    }
    int mid = (l + r) >> 1;
    pair<int, int> ans(0, 0);
    if (tree[rt * 2] <= tree[rt * 2 + 1]) {
        ans = query(rt * 2, l, mid);
    }else {
        ans =  query(rt * 2 + 1, r, mid);
    }
    return ans;
}

// 修改线段树上的值，并维护区间最小值
void modify(int rt, int l, int r, int idx, int val) {
    if (l == r) {
        tree[rt] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (idx <= mid) {
        modify(rt * 2, l, mid, idx, val);
    } else {
        modify(rt * 2 + 1, mid + 1, r, idx, val);
    }
    tree[rt] = min(tree[rt * 2], tree[rt * 2 + 1]);
}

// 并查集的查找操作
int find(int f[], int x) {
    if (f[x] != x) {
        f[x] = find(f, f[x]);
    }
    return f[x];
}

void work() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        left_idx[i] = i;
        right_idx[i] = i;
        left_fa[i] = i;
        right_fa[i] = i;
    }

    while (k--) {
        // 在线段树上查询区间最小值及其下标
        pair<int, int> ans = query(1, 1, n);
        int idx = ans.second;
        cout<<ans.first<<ans.second<<endl;

        // 找到该位置左边和右边相邻的元素
        int left = find(left_fa, idx - 1);
        find(left_idx, idx - 1);
        int right = find(right_fa, idx + 1);
        find(right_idx, idx + 1);

        // 更新并查集
        left_fa[idx] = left;
        right_fa[idx] = right;
        left_idx[idx] = left;
        right_idx[idx] = right;

        // 修改线段树和数组的值
        modify(1, 1, n, idx, 1e18);
        modify(1, 1, n, left, ans.first);
        modify(1, 1, n, right, ans.first);
        a[left] += ans.first;
        a[right] += ans.first;


        for (int i = 1; i <= n; i++) {
        if (left_fa[i] == i) {
            cout << a[i] << " ";
          
        } 
        } cout<<endl;
    }

    // 输出未被删除的元素
    for (int i = 1; i <= n; i++) {
        if (left_fa[i] == i) {
            cout << a[i] << " ";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    while (T--) {
        work();
    }

    return 0;
}