\(\text{「GLR-R3」}\) 惊蛰
\(\text{Link}\)
\(\text{Describe}\)
给定非负整数序列 \(\{a_n\}\)，定义函数 \(f(x,y)\) 为
\[f(x,y)=\begin{cases} x-y,&x\ge y\\ C,&x< y \end{cases}, \]其中 \(C\) 是给定常数。请构造一个不增非负整数序列 \(\{b_n\}\)，最小化
\[\sum_{i=1}^nf(b_i,a_i). \]\(1\le n\le 10^6,0\le a_i,C\le 10^9\)
\(\text{Solution}\)
容易想到一个 \(O(nV)\) 状态的 \(\text{DP}\)，定义 \(g(i,j)\) 为 \(b_i=j\) 的最小权值，转移可以通过后缀和的方法 \(O(1)\).
\[g(i,j)=\min_{k\ge j}g(i-1,k)+f(j,a_i) \]考虑优化状态，一般对于值域很大的 \(\text{DP}\)，一般值域状态只有部分有用，大部分可以省去。贪心地考虑，如果 \(\forall j,b_i\not=a_j\) 那么存在一个不劣的解 \(b'_i\) 满足 \(\exists j,b'_i=a_j\)，我们可以把状态做到 \(O(n^2)\)，记 \(p_k\) 为 \(a_i\) 中第 \(k\) 大的值。
由于我们只要求 \(g(n)\) 且转移 \(g(i)\) 只与 \(g(i-1)\) 有关，所以我们可以考虑转移时用线段树维护 \(g(i)\) 的值，我们记 \(G\) 表示 \(g\) 的后缀最小值，用线段树的区间修改代替 \(O(n)\) 转移。
考虑具体如何转移，我们要实现以下操作。
-
对于 \(p_j<a_i\)，加上 \(C\)
-
对于 \(p_j\ge a_i\)，加上 \(p_j-a_i\)
-
然后滚一个后缀最小值
由于 \(G\) 单调不减，对于前两个操作我们可以二分出一个 \(p\)，在 \([1,p-1]\) 执行第一个操作，\([p+1,n]\) 执行第一个操作。
考虑如何维护第三个操作，因为 \(G\) 单调不减，对于 \([1,p-1]\) 整体平移，单调性不变，而对于 \([p+1,n]\) 加上的 \(p_j-a_i\) 也单调不减，所以 \([p+1,n]\) 单调性不变。
所以我们只需要在 \([1,p-1]\) 用线段树二分找到第一个满足 \(g(i,k)\ge g(i,p)\) 的 \(k\) 然后在 \([k,p-1]\) 上区间覆盖即可。
所以线段树维护 \(\text{DP}\) 转移应该是一个优化转移较简单的 \(\text{DP}\) 的思路。
#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define MAXN (1000005)
#define ll long long
using namespace std;
void File()
{
freopen("C:\\Users\\Administrator\\Desktop\\Code\\IO\\input.txt","r",stdin);
freopen("C:\\Users\\Administrator\\Desktop\\Code\\IO\\output.txt","w",stdout);
}
template<typename type>
void read(type &x)
{
x=0;char ch=0;bool f=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
template<typename type,typename... Args>
void read(type &t,Args &... args)
{
read(t);
read(args...);
}
int n;
int l[MAXN<<2],r[MAXN<<2];
ll C;
ll a[MAXN],val[MAXN],f[MAXN<<2],tag[MAXN<<2],sf[MAXN<<2],cov[MAXN<<2];
void build(int p,int L,int R)
{
l[p]=L,r[p]=R,cov[p]=-1;
if(!(L^R)) return;
int mid=L+R>>1;
build(ls(p),L,mid);
build(rs(p),mid+1,R);
}
void upd_cov(int p,ll v)
{
f[p]=v;
cov[p]=v,tag[p]=0,sf[p]=0;
}
void upd_sf(int p,ll v)
{
f[p]+=val[r[p]]*v;
sf[p]+=v;
}
void upd(int p,ll v)
{
f[p]+=v;
tag[p]+=v;
}
void pushdown(int p)
{
if(~cov[p])
{
upd_cov(ls(p),cov[p]);
upd_cov(rs(p),cov[p]);
cov[p]=-1;
}
if(sf[p])
{
upd_sf(ls(p),sf[p]);
upd_sf(rs(p),sf[p]);
sf[p]=0;
}
if(tag[p])
{
upd(ls(p),tag[p]);
upd(rs(p),tag[p]);
tag[p]=0;
}
}
void pushup(int p){f[p]=max(f[ls(p)],f[rs(p)]);}
void cover(int p,int L,int R,ll v)
{
if(L>R) return;
int nL=l[p],nR=r[p];
if(L<=nL&&nR<=R)
{
upd_cov(p,v);
return;
}
pushdown(p);
int mid=nL+nR>>1;
if(L<=mid) cover(ls(p),L,R,v);
if(R>mid) cover(rs(p),L,R,v);
pushup(p);
}
void modify(int p,int L,int R,ll v,bool f)
{
if(L>R) return;
int nL=l[p],nR=r[p];
if(L<=nL&&nR<=R)
{
upd(p,v);
if(f) upd_sf(p,1);
return;
}
pushdown(p);
int mid=nL+nR>>1;
if(L<=mid) modify(ls(p),L,R,v,f);
if(R>mid) modify(rs(p),L,R,v,f);
pushup(p);
}
ll ask(int p,int x)
{
int nL=l[p],nR=r[p];
if(!(nL^nR)) return f[p];
pushdown(p);
int mid=nL+nR>>1;ll res;
if(x<=mid) res=ask(ls(p),x);
else res=ask(rs(p),x);
pushup(p);
return res;
}
int find(int p,int lim,ll v)
{
int nL=l[p],nR=r[p];
if(nR<=lim&&f[p]<v) return -1;
if(!(nL^nR)) return nL;
int mid=nL+nR>>1;
pushdown(p);
ll res=find(ls(p),lim,v);
if(~res)
{
pushup(p);
return res;
}
res=mid<lim?find(rs(p),lim,v):(-1);
pushup(p);
return res;
}
int main()
{
File();
read(n,C);
for(int i=1;i<=n;i++)
{
read(a[i]);
val[i]=a[i];
}
sort(val+1,val+n+1);
build(1,1,n);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(val+1,val+n+1,a[i])-val;
modify(1,pos+1,n,-a[i],1);
if(pos<=1) continue;
modify(1,1,pos-1,C,0);
ll T=ask(1,pos);
int t=find(1,pos-1,T);
if(~t) cover(1,t,pos-1,T);
}
printf("%lld",ask(1,1));
}