好厉害的题。去年打比赛拿了 60 暴力，今年考古补了。
首先有结论 $\forall i\in[1,n],\exists b_i=a_j$，可以类似归纳法的方式证明。
证明：对于 $i=1$，若 $b_1\geq a_1$，则令 $b_1$ 为最大的 $a_j$ 最优。 若 $b_1<a_1$，则令 $b_1$ 为小于 $a_1$ 的最大的 $a_j$ 最优。因为 $b_1$ 已经取到了它能取到的有意义的最大值，$b_1$ 再变大也不会令之后的决策集合扩大。
对于 $i\not=1$，若 $b_{i-1}$ 满足上述结论，则当 $b_i\geq a_i$ 时令 $b_i=b_{i-1}$ 最优。 若 $b_i<a_i$，仍然令 $b_i$ 为小于 $a_1$ 的最大的 $a_j$ 最优，证明方式同上。
有了这个结论，我们可以将其离散化，记 $val_v$ 是 $v$ 离散化前的值，这样 $f_{i,j}$ 表示第 $i$ 个位置的值为 $num_j$ 时的最小代价，转移方程是：
\[f_{i,j}=\min_{k=j}^{V}f_{i-1,k}+ \begin{cases} val_j-val_{a_i}\quad\quad j\geq a_i\\ C\quad\quad\quad\quad\quad\quad \;j<a_i \end{cases}\]暴力转移是 $\mathcal O(n^3)$，发现转移区间是一个后缀，直接设 $f_{i,j}$ 为后缀 $\min$，把 $i$ 滚掉，方程变为：
\[f_{j}=f_{j}+ \begin{cases} val_j-val_{a_i}\quad\quad j\geq a_i\\ C\quad\quad\quad\quad\quad\quad \;j<a_i \end{cases}\]做完这个后在扫一遍更新后缀 $\min$，可以做到 $\mathcal O(n^2)$。
继续观察转移方程，对于 $j<a_i$ 的情况是平凡的，就是一个区间加，对于 $j\geq a_i$，可以把 $-val_{a_i}$ 拆出来，也是一个区间加（减），考虑 $val_j$ 如何处理。难道是 KTT
$val$ 和 $f$ 都有一个重要的性质：非严格单增。一个区间的 $f$ 的最做单的位置一定是最小值，这样对于一个区间加了一个 $val$ 之后，最小值仍然是最左端的位置。
对于最后后缀 $\min$ 的更新，$f$ 数组下标 $<a_i$ 的部分单增，后半部分也是单增，所以可以在左半部分找出一个分界点，分界点左边的值不需要更新，右边的部分直接区间推平即可。
最优发现这些操作线段树大部分都是好做的。对于第二个操作，发现标记是满足结合律的，并且打了标记之后可以快速知道这个区间的答案，所以这个线段树也可以维护。
复杂度 $\mathcal O(n\log n)$。
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
int n,C,len,ans=INF,numa[1000001],a[1000001];
namespace Segment
{
struct{int l,r,minn,tag1,tag2,tag3;}t[10000001];
inline void update(int p){t[p].minn=min(t[p*2].minn,t[p*2+1].minn);}
inline void down1(int p,int v){t[p].minn=v,t[p].tag2=t[p].tag3=0,t[p].tag1=v;}
inline void down2(int p,int v){t[p].minn+=v,t[p].tag2+=v;}
inline void down3(int p,int v){t[p].minn+=v*numa[t[p].l],t[p].tag3+=v;}
inline void spread(int p)
{
if(t[p].tag1!=-1)down1(p*2,t[p].tag1),down1(p*2+1,t[p].tag1),t[p].tag1=-1;
if(t[p].tag2)down2(p*2,t[p].tag2),down2(p*2+1,t[p].tag2),t[p].tag2=0;
if(t[p].tag3)down3(p*2,t[p].tag3),down3(p*2+1,t[p].tag3),t[p].tag3=0;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].tag1=-1;
if(l==r)return;
int mid=l+((r-l)>>1);
build(p*2,l,mid),build(p*2+1,mid+1,r),update(p);
}
int ask(int p,int x)
{
if(t[p].l==t[p].r)return t[p].minn;
return spread(p),x<=t[p*2].r?ask(p*2,x):ask(p*2+1,x);
}
void change(int p,int l,int r,int k)
{
if(l<=t[p].l&&r>=t[p].r)return down1(p,k);
spread(p);
if(l<=t[p*2].r)change(p*2,l,r,k);
if(r>t[p*2].r)change(p*2+1,l,r,k);
update(p);
}
void modify(int p,int l,int r,int k)
{
if(l<=t[p].l&&r>=t[p].r)return t[p].minn+=k,t[p].tag2+=k,void();
spread(p);
if(l<=t[p*2].r)modify(p*2,l,r,k);
if(r>t[p*2].r)modify(p*2+1,l,r,k);
update(p);
}
void add(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)return down3(p,1);
spread(p);
if(l<=t[p*2].r)add(p*2,l,r);
if(r>t[p*2].r)add(p*2+1,l,r);
update(p);
}
int L;
void check(int p,int val)
{
if(t[p].l==t[p].r)
{
if(t[p].minn>=val)L=min(L,t[p].l);
return;
}
spread(p);
if(t[p*2+1].minn>val)L=min(L,t[p*2+1].l),check(p*2,val);
else check(p*2+1,val);
}
void solve(int p,int k,int val)
{
if(t[p].l==t[p].r)
{
if(t[p].minn>val)L=min(L,t[p].l);
return;
}
spread(p);
if(k>t[p*2].r)
{
if(t[p*2+1].minn>val)check(p*2,val);
solve(p*2+1,k,val);
}
else
solve(p*2,k,val);
}
void print(int p)
{
if(t[p].l==t[p].r)return write(t[p].minn);
spread(p),print(p*2),print(p*2+1);
}
}
using namespace Segment;
inline void mian()
{
read(n,C);int x;
for(int i=1;i<=n;++i)read(a[i]),numa[i]=a[i];
sort(numa+1,numa+1+n),len=unique(numa+1,numa+1+n)-numa-1,build(1,1,len);
for(int i=1;i<=n;++i)
{
a[i]=lower_bound(numa+1,numa+1+len,a[i])-numa;
if(a[i]-1)
{
x=ask(1,a[i]),L=inf;
solve(1,a[i]-1,x-C);
modify(1,1,a[i]-1,C);
L!=inf?change(1,L,a[i]-1,x):void();
}
modify(1,a[i],n,-numa[a[i]]),add(1,a[i],n);
}
write(t[1].minn);
}