「WyOJ Round 1」归 · 星穗垂野
Pigsyy
·
·
题解
Solution
算法标签：动态规划、可持久化线段树。
O(n^3)
令 f_{i,j} 表示前 i 个数中，选择的最后一段（注意该段的末尾可以不为 i）的长度为 j 的最小代价，转移如下：
f_{i,j}=\min
\begin{cases}
& f_{i-j,k}+\gcd(a_{i-j+1},\dots,a_i)\times \sum_{i=l}^r b_i+C)\quad k\le \gcd\le j\\
& f_{i-1,j}
\end{cases}
其中 \gcd 和 \sum 可分别通过 ST 表和前缀和维护，这样查询时复杂度为 O(1)。
O(n\log n\log V)
性质：\gcd 只有 \log V 种不同的值（因为 \gcd 相当于质因数集合取交，而至多只有 \log V 个质因数）。
注意到，若 \gcd 相同，则 j 越小越好。原因如下：
-
- 转移中有 f_{i,j}=f_{i-1,j}，所以 k 相同的情况下，i-j 值越大必然 f_{i-j,k} 越小。而且 \gcd 相同的情况 k 的范围是一样的。
综上，j 越小越好，也就是只需要转移 \log V 种 j 的值。不过，这 \log V 种不一定全都是在 \gcd 第一次变成某个值的时候，因为有 \gcd\le j 的条件，这里找到第一个 \ge \gcd 的 j 即可。
接下来，考虑到 k 的可取范围是一个区间，j 相当于单点修。于是，不难想到将第二维放到线段树上。不过，由于第一维每次取的是 f_{i-j}，所以需要可持久化线段树。
时空复杂度均为 $O(n\log n\log V)$。
## Code 1
```cpp
// std
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class T>
void ckmn(T &a, T b) {
a = min(a, b);
}
template <class T>
T gcd(T a, T b) {
return !b ? a : gcd(b, a % b);
}
const int maxn = 1e5 + 5;
int n;
i64 C;
int a[maxn];
i64 b[maxn];
i64 preb[maxn];
i64 sum(int l, int r) {
return preb[r] - preb[l - 1];
}
struct ST {
int _gcd[18][maxn];
void init() {
for (int i = 1; i <= n; i++) {
_gcd[0][i] = a[i];
}
for (int i = 1; i <= 17; i++) {
for (int j = 1; j <= n - (1 << i) + 1; j++) {
_gcd[i][j] = gcd(_gcd[i - 1][j], _gcd[i - 1][j + (1 << i - 1)]);
}
}
}
int query(int l, int r) {
int _ = __lg(r - l + 1);
return gcd(_gcd[_][l], _gcd[_][r - (1 << _) + 1]);
}
} st;
struct HJT {
struct Node {
int ls, rs;
i64 mn;
} nd[32400005];
int ndcnt;
void pushup(Node &x) {
x.mn = min(nd[x.ls].mn, nd[x.rs].mn);
}
void build(int &rt, int l, int r) {
if (!rt)
rt = ++ndcnt;
nd[rt].mn = 1e18;
if (l == r) {
return;
}
int mid = (l + r >> 1);
build(nd[rt].ls, l, mid);
build(nd[rt].rs, mid + 1, r);
}
void change(int &rtold, int &rtnew, int l, int r, int x, i64 _v) {
if (!rtnew) {
rtnew = ++ndcnt;
nd[rtnew].mn = nd[rtold].mn;
}
if (l == r) {
ckmn(nd[rtnew].mn, _v);
return;
}
int mid = (l + r >> 1);
if (mid >= x) {
if (nd[rtnew].ls == nd[rtold].ls)
nd[rtnew].ls = 0;
change(nd[rtold].ls, nd[rtnew].ls, l, mid, x, _v);
} else {
if (nd[rtnew].rs == nd[rtold].rs)
nd[rtnew].rs = 0;
change(nd[rtold].rs, nd[rtnew].rs, mid + 1, r, x, _v);
}
if (!nd[rtnew].ls)
nd[rtnew].ls = nd[rtold].ls;
if (!nd[rtnew].rs)
nd[rtnew].rs = nd[rtold].rs;
pushup(nd[rtnew]);
}
i64 query(int rt, int curl, int curr, int l, int r) {
if (!rt)
return 1e18;
if (curl >= l && curr <= r) {
return nd[rt].mn;
}
int mid = (curl + curr >> 1);
i64 ans = 1e18;
if (mid >= l)
ckmn(ans, query(nd[rt].ls, curl, mid, l, r));
if (mid < r)
ckmn(ans, query(nd[rt].rs, mid + 1, curr, l, r));
return ans;
}
} ds;
int rt[maxn];
void solve(int id_of_test) {
cin >> n >> C;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
st.init();
for (int i = 1; i <= n; i++) {
cin >> b[i];
preb[i] = preb[i - 1] + b[i];
}
ds.build(rt[0], 1, 100000);
for (int r = 1; r <= n; r++) {
rt[r] = ++ds.ndcnt;
ds.nd[rt[r]] = ds.nd[rt[r - 1]];
int ok = 0;
int efl = 1, efr = r;
while (efl <= efr) {
int mid = (efl + efr >> 1);
if (r - mid + 1 >= st.query(mid, r)) {
ok = mid;
efl = mid + 1;
} else {
efr = mid - 1;
}
}
if (!ok) continue;
int l = ok;
int _gcd = st.query(l, r);
while (l >= 1) {
if (r - l + 1 >= _gcd) {
i64 tot = 1ll * _gcd * sum(l, r);
i64 ans = tot;
ckmn(ans, tot + C + ds.query(rt[l - 1], 1, 100000, 1, _gcd));
ds.change(rt[r - 1], rt[r], 1, 100000, r - l + 1, ans);
}
int efl = 1, efr = l;
int ok = l;
while (efl <= efr) {
int mid = (efl + efr >> 1);
int k = __lg(r - mid + 1);
if (st._gcd[k][mid] % _gcd != 0 || st._gcd[k][r - (1 << k) + 1] % _gcd != 0) {
efl = mid + 1;
} else {
ok = mid;
efr = mid - 1;
}
}
l = ok - 1;
if (l)
_gcd = st.query(l, r);
}
}
cout << ds.query(rt[n], 1, 100000, 1, 100000) + C << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
for (int _ = 1; _ <= T; _++) {
solve(_);
}
return 0;
}
```
## Code 2
```cpp
// 验题人（KSCD_）的代码
#include<iostream>
#define ll long long
using namespace std;
const int N=1e5+10;
const int K=18;
const ll inf=2e18;
int n,a[N],rt[N]; ll C,s[N];
int gcd(int a,int b) {return (b?gcd(b,a%b):a);}
struct ST
{
int w[N][K],lg[N],po[K];
void build()
{
lg[0]=-1,po[0]=1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1,w[i][0]=a[i];
for(int i=1;i<18;i++) po[i]=po[i-1]*2;
for(int k=1;po[k]<=n;k++) for(int i=1;i+po[k]-1<=n;i++)
w[i][k]=gcd(w[i][k-1],w[i+po[k-1]][k-1]);
}
int query(int l,int r)
{
int k=lg[r-l+1];
return gcd(w[l][k],w[r-po[k]+1][k]);
}
}Ta;
struct Exsgmtt
{
int t,lc[N*K*K],rc[N*K*K]; ll w[N*K*K];
int build(int l,int r)
{
int u=++t; w[t]=inf;
if(l<r)
{
int mid=((l+r)>>1);
lc[u]=build(l,mid),rc[u]=build(mid+1,r);
}
return u;
}
int update(int u,int l,int r,int p,ll x)
{
int v=++t; w[v]=min(w[u],x),lc[v]=lc[u],rc[v]=rc[u];
if(l<r)
{
int mid=((l+r)>>1);
if(p<=mid) lc[v]=update(lc[v],l,mid,p,x);
else rc[v]=update(rc[v],mid+1,r,p,x);
}
return v;
}
ll query(int u,int l,int r,int L,int R)
{
if(l>=L&&r<=R) return w[u];
ll res=inf; int mid=((l+r)>>1);
if(L<=mid) res=min(res,query(lc[u],l,mid,L,R));
if(R>mid) res=min(res,query(rc[u],mid+1,r,L,R));
return res;
}
}T;
void sol()
{
cin>>n>>C,T.t=0,T.build(0,n),rt[0]=T.update(1,0,n,0,0);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1,x;i<=n;i++) cin>>x,s[i]=s[i-1]+x;
Ta.build();
for(int i=1;i<=n;i++)
{
int L=1,R; rt[i]=rt[i-1];
while(L<=i)
{
int k=Ta.query(i-L+1,i),l=L,r=i; R=L;
while(l<=r)
{
int mid=((l+r)>>1);
if(Ta.query(i-mid+1,i)==k) R=mid,l=mid+1;
else r=mid-1;
}
if(k<=R)
{
int j=max(k,L);
ll f=T.query(rt[i-j],0,n,0,k)+1ll*k*(s[i]-s[i-j])+C;
rt[i]=T.update(rt[i],0,n,j,f);
}
L=R+1;
}
}
cout<<T.query(rt[n],0,n,1,n)<<'\n';
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int TT; cin>>TT;
while(TT--) sol();
return 0;
}
```