``` #include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pii; const int N=5e5+10; int a[N],l[N],r[N]; int st[N]; void solve(){ int n,k; cin>>n>>k; priority_queue<pii,vector<pii>,greater<pii>>q; for(int i=0;i<n;i++){ cin>>a[i]; q.push({a[i],i}); st[i]=a[i]; l[i]=i-1; r[i]=i+1; if(r[i]==n) r[i]=-1; } while(k){ pii t=q.top(); q.pop(); if(t.first!=st[t.second]){ q.push({st[t.second],t.second}); continue; } k--; int pos=t.second; if(l[pos]>=0) st[l[pos]]+=t.first; if(r[pos]>=0) st[r[pos]]+=t.first; if(l[pos]>=0) r[l[pos]]=r[pos]; if(r[pos]>=0) l[r[pos]]=l[pos]; st[pos]=-1; } for(int i=0;i<n;i++){ if(st[i]!=-1){ cout<<st[i]<<" "; } } cout<<endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while(t--) solve(); return 0; } ```

``` #include <bits/stdc++.h> #define int long long #define int long long #define x first #define y second using namespace std; const int N = 5e5 + 10; int n, k; int l[N], r[N]; int a[N]; priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int, int>>> aa; signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; r[0] = 1; for(int i = 1; i <= n; i ++ ) { cin >> a[i]; aa.push({a[i], i}); l[i] = i - 1, r[i] = i + 1; } while(k -- ) { auto t = aa.top(); aa.pop(); if(t.x != a[t.y]) aa.push({a[t.y], t.y}), k++; else{ r[l[t.y]] = r[t.y], l[r[t.y]] = l[t.y]; a[l[t.y]] += a[t.y], a[r[t.y]] += a[t.y]; } } int t = r[0]; while(t != n + 1) { cout << a[t] << " "; t = r[t]; } } ```

import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Main { ``` static int N = 500_100; static long[] a = new long[N]; static int [] l = new int[N]; static int [] r = new int[N]; static long n,k; public static class Pair implements Comparable<Pair>{ long val; int idx; Pair(long val,int idx){ this.val=val; this.idx=idx; } @Override public int compareTo(Pair o) { // TODO Auto-generated method stub return Long.compare(this.val, o.val); } } public static void main(String[] args) { PriorityQueue<Pair> heap = new PriorityQueue<>(); Scanner scanner = new Scanner(System.in); n = scanner.nextLong(); k = scanner.nextLong(); List<Pair> list = new LinkedList<>(); for (int i = 1; i <= n; i++) { a[i]=scanner.nextLong(); heap.add(new Pair(a[i], i)); l[i]=i-1; r[i]=i+1; } r[0]=1; while(k>0&&!heap.isEmpty()) { Pair p = heap.poll(); long val = p.val; int pos = p.idx; if(val!=a[pos]) { continue; } k--; if(l[pos]>=1) { a[l[pos]]+=val; heap.add(new Pair(a[l[pos]], l[pos]));//放进小跟堆 会一直排序 } if(r[pos]<=n) { a[r[pos]]+=val; heap.add(new Pair(a[r[pos]], r[pos])); } //断开原来pos的值 r[l[pos]]=r[pos]; l[r[pos]]=l[pos]; } for (int i = r[0]; i <= n; i=r[i]) { System.out.print(a[i]+" "); } } ``` }

优先队列 ``` #include<bits/stdc++.h> using namespace std; #define val first #define pos second typedef long long ll; typedef pair<ll,int>PLI; const int MAX_N = 5e5 + 5;//链表 int N, K, pre[MAX_N], nxt[MAX_N]; ll A[MAX_N]; priority_queue<PLI>q;//优先队列 int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//取消同步流,让C++代码更快 cin>>N>>K; for(int i = 1;i<=N;++i) { cin>>A[i]; pre[i] = i - 1; nxt[i] = i + 1; q.push({-A[i], -i}); } pre[1] = -1;//不存在 nxt[N] = -1;//不存在 while(K--) { PLI now; do { now = q.top(); q.pop(); now.val = -now.val; now.pos = -now.pos; }while(A[now.pos] != now.val); int PRE = pre[now.pos]; int NXT = nxt[now.pos]; if(PRE != -1) { A[PRE] += now.val; q.push({-A[PRE],-PRE}); nxt[PRE] = NXT; } if(NXT != -1) { A[NXT] += now.val; q.push({-A[NXT],-NXT}); pre[NXT] = PRE; } A[now.pos] = -1; } for(int i = 1;i <= N;++i) { if(A[i] != -1) { cout<<A[i]<<' '; } } return 0; } ```

import sys import heapq import time from math import sqrt,gcd sys.setrecursionlimit(10000) input=lambda:sys.stdin.readline().strip() def del_func(x, v, l, r): r[l[x]] = r[x] l[r[x]] = l[x] v[l[x]] += v[x] v[r[x]] += v[x] n, k = map(int, sys.stdin.readline().split()) v = [0] (n + 2) l = [0] (n + 2) r = [0] (n + 2) h = [] r[0] = 1 l[n + 1] = n nums = [int(n) for n in sys.stdin.readline().split()] for i in range(1, n + 1): v[i] = nums[i - 1]#int(input()) l[i] = i - 1 r[i] = i + 1 heapq.heappush(h, (v[i], i)) while k > 0: p = heapq.heappop(h) if p[0] != v[p[1]]: heapq.heappush(h, (v[p[1]], p[1])) k += 1 else: del_func(p[1], v, l, r) k -= 1 head = r[0] while head != n + 1: sys.stdout.write(str(v[head]) + " ") head = r[head]

``` #include <bits/stdc++.h> #define endl '\n' typedef long long ll; using namespace std; //数据结构在这里定义 const int N =1e5+5; int n,k; ll A[N];//存原数组的值 int L[N],R[N]={1}; //左右数组用于O(1)复杂度获取某个元素的前后元素 //同时O(1)复杂度删除该元素 struct node{ int idx; int val; node(int idx, int val):idx(idx),val(val) {} //小顶堆重载>里面也是> bool operator>(const node& other) const{ return val==other.val?idx>other.idx:val>other.val; } }; //每次从堆顶拿一个元素就是题目要删除的 priority_queue<node, vector<node>, greater<node>> pq; void solve(){ //cin cout在这里 cin >> n >> k; for(int i = 1 ; i <= n; i++){ cin >> A[i]; L[i] = i - 1; R[i] = i + 1; pq.push(node(i, A[i])); } // while(!pq.empty()){ // node cur = pq.top(); pq.pop(); // printf("A[%d] = %d\n",cur.idx,cur.val); // } // for(int i = R[0];i<=n;i=R[i]){ // cout << A[i] << " "; // } while(1){ node cur = pq.top(); pq.pop(); //有可能这个结点是旧结点，之前的删除操作改变了其值 if(A[cur.idx] != cur.val) continue; //在模拟双向链表上删除结点,并修改左右结点的值 //0和n+1视为特殊边界 if(L[cur.idx] >= 1){//说明有左结点 // R[L[cur.idx]] = R[cur.idx]; A[L[cur.idx]] += cur.val; //更新后的结点需要重新进入队列，重新排列 pq.push(node(L[cur.idx], A[L[cur.idx]])); } if(R[cur.idx] <= n){ // L[R[cur.idx]] = L[cur.idx]; A[R[cur.idx]] += cur.val; pq.push(node(R[cur.idx], A[R[cur.idx]])); } //操作完一次 k-- //这个链表更新操作不能放到上面的if里 //不管左右还有没有结点都得更新 //这样才能正确的指向 0 和 n+1表示这是最后一个元素了 R[L[cur.idx]] = R[cur.idx]; L[R[cur.idx]] = L[cur.idx]; k--; if(k==0) break; } for(int i = R[0]; i <= n; i = R[i]){ cout << A[i] << " "; } cout << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;//多组数据要cin //cin >> t; t = 1; while(t--){ solve(); } return 0;//必须加return 0 } ```

3092. 最高频率的 ID - 力扣（LeetCode） 有点这个题的懒删除堆的写法😕 ```C++ #include <cstdio> #include <queue> #include <vector> #include <utility> #include <functional> #include <list> using namespace std; using ll = long long; int main() { int n, k; scanf("%d %d", &n, &k); auto cmp = []( const pair<ll, pair<int, list<ll>::iterator>>& a, const pair<ll, pair<int, list<ll>::iterator>>& b) { if (a.first == b.first) return a.second.first > b.second.first; return a.first > b.first; }; // key 从小到大, 相同 则 val 从小到大 list<ll> arr; priority_queue< pair<ll, pair<int, list<ll>::iterator>>, vector<pair<ll, pair<int, list<ll>::iterator>>>, decltype(cmp)> pq(cmp); for (int i = 0; i < n; ++i) { ll j; scanf("%lld", &j); arr.push_back(j); pq.push(make_pair(j, make_pair(i, --arr.end()))); } while (k--) { auto x = pq.top(); pq.pop(); if (x.first != *(x.second.second)) { pq.push(make_pair(*(x.second.second), make_pair(x.second.first, x.second.second))); ++k; continue; } // f - s // 对 arr 进行修改: // 删除了 x // 获取 这个数的前一个数 auto mae = x.second.second; if (arr.begin() != mae) { // 给前面一个数进行加 --mae; *mae += *(x.second.second); } auto next = x.second.second; ++next; if (next != arr.end()) { // 给后面一个数进行加 *next += *(x.second.second); } // 移除自己 arr.erase(x.second.second); // printf("%lld [%d, %p]\n", x.first, x.second.first, x.second.first); } for (ll& it : arr) printf("%lld ", it); return 0; } ```