题目传送门
借鉴这篇题解，dalao%%%
如果我们真的模拟的话肯定过不了的（记录）。
所以我们可以使用链表+优先队列的方式，来记录这个数列。
其中的删除操作也不是让我们真的删去，用版本（version）的方式记录当前数据能不能用，不能用就弹出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=500010;
#define int long long
int n,k;
int a[MAXN];
struct LIST
{
int pre,nxt;
}lst[MAXN];
struct node
{
int id;
int val;
int ver;
bool operator <(const node &a)const
{
if(val==a.val)return id>a.id;
else return val>a.val;
}
};
priority_queue <node> q;
int v[MAXN];
bool isdel[MAXN];
int read()
{
int x=0,f=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void print(int x)
{
if(x<0)x=-x;
if(x<10)putchar(x+'0');
else print(x/10),putchar(x%10+'0');
}
signed main()
{
n=read(),k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
q.push({i,a[i],0});
lst[i]={i-1,i+1};
}
lst[1].pre=lst[n].nxt=-1;
for(int vers=1;vers<=k;vers++)
{
while(!q.empty()&&q.top().ver!=v[q.top().id])q.pop();
node front=q.top();
q.pop();
int id=front.id;
isdel[id]=1;
int val=front.val;
int pre=lst[id].pre,nxt=lst[id].nxt;
if(pre!=-1)
{
lst[pre].nxt=nxt;
a[pre]+=val;
q.push({pre,a[pre],vers});
v[pre]=vers;
}
if(nxt!=-1)
{
lst[nxt].pre=pre;
a[nxt]+=val;
q.push({nxt,a[nxt],vers});
v[nxt]=vers;
}
}
for(int i=1;i<=n;i++)
if(!isdel[i])printf("%lld ",a[i]);
return 0;
}
|