46 lines
1.4 KiB
C++
46 lines
1.4 KiB
C++
// lanqiao3515 整数删除(优先队列+链表) 优先队列维护最值log(n), 链表删除O(1), 总时间复杂度O(nlogn)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
const int N = 5e5 + 10;
|
|
typedef pair<int, int> pr;
|
|
struct{ int v, pre, nxt; } a[N];
|
|
int res[N];
|
|
int update[N]; // update[id]记录下标id的元素是否更新
|
|
signed main(){
|
|
priority_queue<pr, vector<pr>, greater<pr>> pq; // 小根堆
|
|
int n, k; cin >> n >> k;
|
|
for(int i = 1; i <= n; i++){
|
|
int x; cin >> x;
|
|
a[i].pre = i - 1, a[i].nxt = i + 1, a[i].v = x;
|
|
pq.push({make_pair(x, i)});
|
|
}
|
|
while(pq.size() > n - k){
|
|
pr cur = pq.top(); pq.pop(); //堆维护最值 O(logn)
|
|
int id = cur.second, w = cur.first;
|
|
if(update[id]){ //更新之前的某个值
|
|
pq.push(make_pair(w + update[id], id));
|
|
update[id] = 0;
|
|
}else{ //更新左右
|
|
int l = a[id].pre, r = a[id].nxt;
|
|
update[l] += w;
|
|
update[r] += w;
|
|
// 链表的删除-O(1)
|
|
a[l].nxt = r;
|
|
a[r].pre = l;
|
|
}
|
|
}
|
|
while(!pq.empty()){
|
|
pr cur = pq.top(); pq.pop();
|
|
int id = cur.second, w = cur.first;
|
|
res[id] = w + update[id];
|
|
}
|
|
for(int i = 1; i <= n; i++){
|
|
if(res[i]) cout << res[i] << ' ';
|
|
}
|
|
return 0;
|
|
}
|
|
/* test samples -> 17 7
|
|
5 3
|
|
1 4 2 8 7
|
|
*/ |