【2023成都集训模拟赛04】op 做题记录

给定两个正整数 $n,k$ 和一个长度为 $n$ 的整数序列 $a_i$，你需要进行任意次下列操作把所有 $a_i$ 变成 $0$：

• 选择一段长度为 $k$ 的区间 $[l,r]$ 和一个正整数 $E$，把 $a_{[l,r]}$ 中所有小于等于 $E$ 的数改为 $0$；

最小化所有操作的 $E$ 的和。

对于每一个 $a$ 的前缀 $a_{[1,i]}$，你要求出它的答案 $f_{i}$，输出 $\sum\limits_{i=1}^nf_i23^{n-i}\mod (10^9+7)$。

$1\le n\le 10^7$，$1\le a_i\le 2\times 10^9$，时间复杂度要求线性。

原题 $n\le 2.5\times 10^6$ 时限 $0.25\text{ S}$ 放了 $O(n\log n)$ 过。

考虑一个朴素的 dp，设 $f_i$ 为 $a_{[1,i]}$ 的答案。由于每次操作可以看作花费 $\max\limits_{l\le i\le r} a_i$ 的代价把满足 $r-l+1\le k$ 的 $a_{[l,r]}$ 变成 $0$，所以转移可以考虑枚举把 $a_i$ 变成 $0$ 的那次操作的 $l$：

$f_i=\min\limits_{j=\max(1,i-k+1)}^{i} \{f_{j-1}\max\limits_{j\le p\le i} a_p\}$

显然 $f_i$ 单调递增，所以只统计满足 $a_p>\max\limits_{p<l\le i} a_l$ 的 $f_{p-1}+a_p$ 的最小值即可。

这样的 $p$ 可以很方便地用单调队列维护，但是发现由于单调队列中既会加入会删除，$f_{p-1}+a_p$ 只能 $O(\log n)$ 维护。

考虑优化，发现满足 $p\le i,i-p\le k$ 的 $p$ 才对 $f_i$ 有贡献，所以考虑按 $k$ 分块（$[1,k]$、$[k+1,2k]$ 等等为一块）。设 $S$ 为合法的 $p$ 构成的集合，则：

• 贡献可以分为块内贡献和块间（$i$ 所在块和上一块）贡献；
• 块内贡献：正着扫，$S$ 中只会加入新元素；
• 块间贡献：倒着扫，$S$ 中同样只会加入新元素；

注意要先处理块间贡献。

时间复杂度 $O(n)$，实测 $10^7$ 只跑了 $0.9\text{ S}$，不知道为什么原题不开 $n\le 10^7$ 时限 $1\text{ S}$。

还可以双栈。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() { 
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}

const int S=10000005,p=1000000007;
const long long inf=1e17;

int n,k,a[S],_23[S];
long long f[S];
int top,sta[S];
long long stb[S];
int mx[S],tot,mxp[S];

int main()
{
	freopen("op.in","r",stdin);
	freopen("op.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	_23[0]=1;
	for(int i=1;i<=n;i++) _23[i]=1ll*_23[i-1]*23%p;
	#define R(x) (min(n,((x-1)/k+1)*k))
	f[0]=0;
	for(int i=1;i<=n;i++) f[i]=inf;
	for(int l=1;l<=n;l=R(l)+1)
	{
		int r=R(l);
		// 上一块 - 当前块
		if(l>1)
		{
			int l2=l-k,r2=l-1;
			mx[l-1]=0;
			for(int i=l;i<=r;i++) mx[i]=max(mx[i-1],a[i]);
			tot=0;
			for(int i=r2,mx=0;i>=l2;i--) if(a[i]>mx) mx=a[i],mxp[++tot]=i;
			long long mn=inf;
			for(int i=r,lb=1,rb=-1;i>=l;i--)
			{
				int p=i-k;
				while(lb<=tot&&mxp[lb]>=p)
				{
					if(mx[i]<=a[mxp[lb]])
					{
						if(rb==-1) rb=lb;
						else mn=min(mn,f[mxp[lb]]+a[mxp[lb-1]]);
					}
					lb++;
				}
				if(rb==-1&&mx[i]<=a[mxp[lb-1]]) rb=lb-1;
				if(rb!=-1)
				{
					while(rb-1<=tot&&a[mxp[rb-1]]>=mx[i])
					{
						mn=min(mn,f[mxp[rb]]+a[mxp[rb-1]]);
						rb--;
					}
				}
				f[i]=min(f[i],min(mn,min(
					f[p]+max(a[mxp[lb-1]],mx[i]),
					rb!=-1?f[mxp[rb]]+mx[i]:inf
				)));
			}
		}
		// 当前块内
		top=0,sta[0]=l-1,stb[0]=inf;
		for(int i=l;i<=r;i++)
		{
			while(top>0&&a[sta[top]]<a[i]) top--;
			top++;
			sta[top]=i,stb[top]=min(stb[top-1],f[sta[top-1]]+a[i]);
			f[i]=min(f[i],stb[top]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans+1ll*f[i]%p*_23[n-i]%p)%p;
	printf("%d\n",ans);
	return 0;
}