自动搬运

查看原文

来自洛谷，原作者为

	harmis_yz beiribaol，幻想，永恒。

搬运于2025-08-24 23:13:52，当前版本为作者最后更新于2025-04-18 23:06:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思维难度：没有。

代码难度：绿。

建议评级：蓝。

分析

考虑 DP。

定义状态函数 $f_{i,j}$ 表示前 $i$ 个数划分，最后一个区间长度为 $j$ 时候的最小值。

注意到这题给了很多个 $\gcd$，那有个典的东西就是对于同一个 $r$，关于 $l$ 不同的 $\gcd$ 值只有 $O(\log V)$ 个。因为 $l \to l-1$，$\gcd$ 要么不变，要么至少变成原来的 $\frac{1}{2}$（删至少一个质因子）。我们枚举 $r$，枚举 $\gcd$ 的值（记为 $x$）。那么可以得到一个合法的 $l$ 区间 $[L,R]$（$r-l+1\ge x \land \gcd(a_l,a_{l+1},\dots,a_r)=x$）。对于这里面的任意一个 $l$，都有转移方程：$f_{r,r-l+1}=\min(f_{r-1,r-l+1},\min\limits_{k=0}^{x}f_{l-1,k}+(x \sum\limits_{i=l}^{r}b_i +C))$。

乍一看很难维护，再一看就可以维护了。为什么呢，简单。我们有：$f_{i,j} \le f_{i-1,j}$。所以 $\min\limits_{k=0}^{x}f_{l-1,k}+(x \sum\limits_{i=l}^{r}b_i +C)$ 一定不小于 $\min\limits_{k=0}^{x}f_{l-2,k}+(x \sum\limits_{i=l-1}^{r}b_i +C)$，因为 $b_{l-1}\ge 0$ 且 $f_{l-2,k}\ge f_{l-1,k}$。同时呢，我们 $f_{i,j}$ 能用来转移 $f_{k,w}$ 时，$f_{i,j-1}$ 也一定能用来转移 $f_{k,w}$（$f_{r,r-l+1}$ 的限制比 $f_{r,r-l+2}$ 松）。所以 $l$ 在 $r$ 和 $x$ 都是定值的时候取 $R$ 就行了。

也就是说，转移方程变成：$f_{r,r-R+1}=\min(f_{r-1,r-R+1},\min\limits_{k=0}^{x}f_{R-1,k}+(x \sum\limits_{i=R}^{r}b_i +C))$。线段树维护即可，时间复杂度 $O(n\log^2n)$。

代码

const int N=1e5+10,inf=1e18;
int n,C;
int a[N],b[N],s[N];
int __[N],Gcd[N][20];
struct Tree{
	int l,r,mi;
}tr[N<<2];
struct node{
	int i,j,delta,k;
};
struct node_{
	int j,k;
};
vector<node_> vec_[N];
vector<node> vec[N];

il void up(int u){
	tr[u].mi=min(tr[ls(u)].mi,tr[rs(u)].mi);
	return ;
}
il void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r,tr[u].mi=inf;
	if(l==r) return ;
	int mid=l+r>>1;
	build(ls(u),l,mid),build(rs(u),mid+1,r);
	return ;
}
il void modify(int u,int x,int y){
	if(tr[u].l==tr[u].r) return tr[u].mi=min(tr[u].mi,y),void(0);
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) modify(ls(u),x,y);
	else modify(rs(u),x,y);
	return up(u),void(0);
}
il int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mi;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid&&mid< r) return min(query(ls(u),l,r),query(rs(u),l,r));
	if(l<=mid) return query(ls(u),l,r);
	return query(rs(u),l,r);
}
il int get_gcd(int l,int r){
	int k=__[r-l+1];
	return gcd(Gcd[l][k],Gcd[r-(1ll<<k)+1][k]);
}

il void solve(){
	n=rd,C=rd;
	for(re int i=0;i<=n;++i) __[i]=log2(i),vec[i].clear(),vec_[i].clear();
	for(re int i=1;i<=n;++i) a[i]=rd,Gcd[i][0]=a[i];
	for(re int i=1;i<=n;++i) b[i]=rd,s[i]=s[i-1]+b[i];
	for(re int j=1;j<20;++j)
	for(re int i=1;i+(1ll<<j)-1<=n;++i) Gcd[i][j]=gcd(Gcd[i][j-1],Gcd[i+(1ll<<(j-1))][j-1]);
	for(re int r=1;r<=n;++r){
		int u=r;
		while(u>=1){
			int gcdd=get_gcd(u,r);
			int le=1,ri=u,w=-1;
			while(le<=ri){
				int mid=le+ri>>1;
				if(get_gcd(mid,r)>=gcdd) w=mid,ri=mid-1;
				else le=mid+1;
			}
			int x=w,y=u;
			//r+1-gcdd>=l
			int l=r+1-gcdd;
			l=min(l,y);
			if(l<x){
				u=x-1;
				continue;
			}
			vec[l-1].push_back({r,r-l+1,gcdd*s[r]-gcdd*s[l-1]+C,gcdd});
			u=x-1;
		}
	}
	build(1,0,N-1);
	vec_[0].push_back({0,0});
	for(re int r=0;r<=n;++r){
		for(auto x:vec_[r]){
			int j=x.j,k=x.k;
			modify(1,x.j,x.k);
		}
		for(auto x:vec[r]){
			int i=x.i,j=x.j,delta=x.delta,k=x.k;
			int Min=query(1,0,k);
			vec_[i].push_back({j,delta+Min});
		}
	}
	printf("%lld\n",query(1,1,N-1));
    return ;
}