算法

双向链表

时间复杂度

应该是O(nlogn)

一些说明

qi[i]:i节点距离前一个节点的偏移量
ne[id]:i节点距离后一个节点的偏移量

代码的小细节：

增加a[0],a[n+1],省去删除首末节点时的特判处理；
当删除的节点值为0时，前后的节点的值不变，不用再次入队，只需改变受影响的偏移量即可；
在找当前最小值时，可能该节点的值已经发生了改变，而找到的是之前的值，直接pop，找下一个最小值，直到找到真的最小值

C++ 代码

#include<iostream>
#include<queue>
#define ll long long
using namespace std;
const int N=500010;
struct node{
    ll num,id;
    bool operator<(const node& n1)const{
        return num==n1.num?id>n1.id:num>n1.num;
    }
};
priority_queue<node>pq;
ll a[N],qi[N],ne[N];
int main(){
    int n,k; scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        pq.push({a[i],i});
        qi[i]=1,ne[i]=1;
    }
    qi[n]=1,ne[0]=1;
    a[0]=1e18,a[n+1]=1e18;
    for(int uu=1;uu<=k;uu++){
        node tmp;
        while(1){
            tmp=pq.top(); pq.pop();
            if(a[tmp.id]==tmp.num) break;
        }
 //       printf("uu=%d  tmp.num=%d  tmp.id=%d\n",uu,tmp.num,tmp.id);
        int qiid=tmp.id-qi[tmp.id];
        int neid=tmp.id+ne[tmp.id];
 //       printf("qiid=%d neid=%d\n",qiid,neid);
        ne[qiid]+=ne[tmp.id];qi[neid]+=qi[tmp.id];
        if(tmp.num){
            a[qiid]+=tmp.num; a[neid]+=tmp.num; 
            pq.push({a[qiid],qiid}); pq.push({a[neid],neid});
        }
    }
    for(int i=ne[0];i<=n;i+=ne[i])
        printf("%lld ",a[i]);
    return 0;
}