补题 | CF2241G
题目
Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128.
For any array b of length m, define f(b) as the minimum possible value of \max(b) - \min(b) that can be achieved by performing the following operation any number of times:
- Choose any index 1 \le i \lt m, and do exactly one of the following:
- Set b_{i+1} := b_{i+1} + b_i,
- Set b_{i+1} := b_{i+1} - b_i.
You are given an array a of length n. Your task is to compute the sum of f over all the subarrays^{\text{∗}} of a. More formally, determine the value of
^{\text{∗}}An array b is a subarray of an array a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
做法
先考虑二元的做法即 f([b_1,b_2]) ，其中 b_2 可以加减任意倍数的 b_1 ，那么不难发现 f([b_1,b_2])=\min(b_2\mod b_1,b_1-b_2\mod b_1) 。由辗转相除知道 \gcd(a,b)=gcd(a,b\pm a) ，也就是对于前缀数组进行任意操作都不会改变其 \gcd 。记g_r=\gcd(b_1,b_{2} \cdots b_r)，那么 b_k (k>2) 可表示为 b_{k-1}+ng_{k-1} 。将前缀 \gcd 看做整体，即可化为二元问题，只需要把每个数调整到离其前缀 \gcd 的倍数的最小距离即可，即：
特别地，有
对于子数组，记 G_{l,r}=\gcd(a_l,a_{l+1} \cdots a_r) ，子数组的贡献是其右端点从 l+1 到 r 中的代价最大值，即：
因为 a_i 仅会受到其前缀的影响，我们不妨固定右端点枚举左端点，定义 cur_l=f([a_l,\cdots,a_r]) ，设想从 r-1 转移至 r ，由上文论证，cur_l=\max (cur_l,w_l) 。同时容易知道 cur_r=0 。枚举完右端点后累加所有 cur_l (l<r) 就是以 r 为右端点对答案的贡献。
又由于这里 \gcd 的单调性，即扩展端点后前缀 \gcd 不变或者减少到原前缀 \gcd 的一半以上（因为是真因子）。因此不同 \gcd 数量最多是 \log A 。因此可将左端点分为若干段，每一段的 G_{l,r} 值相同，如果某一段 \gcd 值为 G ，那么对这段左端点加入 a_r 的代价都是相同的。
即维护一棵线段树记录 cur ，支持区间中将所有小于 w 的数提升至 w ，并可查询全局和。考虑以下维护方式：
对每个节点维护区间最小值、区间严格次小值、最小值出现次数、区间和。如果 w 小于等于最小值，那么无需操作；如果 w 大于最小值同时小于次小值，那么仅需对最小值加到 w 即可，O(1) 操作；如果 w 大于等于严格次小值，那么需要继续递归到子节点。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+9;
const ll INF=(ll)4e18;
struct SegTree{
struct Node{
int l,r;
ll mn; // 最小值
ll se; // 严格次小值
ll cnt; // 最小值出现次数
ll sum; // 区间和
}tree[maxn<<2];
void pushup(int p){
int L=p<<1,R=p<<1|1;
tree[p].sum=tree[L].sum+tree[R].sum;
if(tree[L].mn==tree[R].mn){
tree[p].mn=tree[L].mn;
tree[p].cnt=tree[L].cnt+tree[R].cnt;
tree[p].se=min(tree[L].se,tree[R].se);
}
else if(tree[L].mn<tree[R].mn){
tree[p].mn=tree[L].mn;
tree[p].cnt=tree[L].cnt;
tree[p].se=min(tree[L].se,tree[R].mn);
}
else{
tree[p].mn=tree[R].mn;
tree[p].cnt=tree[R].cnt;
tree[p].se=min(tree[L].mn,tree[R].se);
}
}
void apply(int p,ll x){ // 最小值提升到 x
if(x<=tree[p].mn) return;
tree[p].sum+=tree[p].cnt*(x-tree[p].mn);
tree[p].mn=x;
}
void pushdown(int p){
ll x=tree[p].mn;
if(tree[p<<1].mn<x){
apply(p<<1,x);
}
if(tree[p<<1|1].mn<x){
apply(p<<1|1,x);
}
}
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].mn=0;
tree[p].se=INF;
tree[p].cnt=1;
tree[p].sum=0;
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
pushup(p);
}
void chmax(int p,int L,int R,ll x){
int l=tree[p].l, r=tree[p].r;
if (R<l||r<L||x<=tree[p].mn){ //区间不包含或无需提升
return;
}
if(L<=l&&r<=R&&x<tree[p].se){ // 包含且小于次小值
apply(p,x);
return;
}
// 继续递归
pushdown(p);
chmax(p<<1,L,R,x);
chmax(p<<1|1,L,R,x);
pushup(p);
}
ll query(){
return tree[1].sum;
}
};
SegTree seg;
struct GcdSeg{
int l,r;
ll g;
};
void print_int128(__int128 x){
if(x==0){
cout<<0;
return ;
}
string s;
while(x>0){
s.push_back(char('0'+x%10));
x/=10;
}
reverse(s.begin(),s.end());
cout<<s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin>>T;
while(T--){
int n;
cin>>n;
vector<ll> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
seg.build(1,1,n);
__int128 ans=0;
vector<GcdSeg> v;
for(int r=1;r<=n;r++){ // 枚举右端点
for(auto [L,R,G]:v){
ll rem=a[r]%G;
ll w=min(rem,G-rem);
seg.chmax(1,L,R,w);
}
ans+=seg.query();
vector<GcdSeg> nv;
for(auto [L,R,G]:v){
ll ng=gcd(G,a[r]);
if(!nv.empty()&&nv.back().g==ng){ // 如果gcd相同且存在段就加入
nv.back().r=R;
} else{
nv.push_back({L,R,ng}); // 更新gcd
}
}
if(!nv.empty()&&nv.back().g==a[r]){
nv.back().r=r;
} else{
nv.push_back({r,r,a[r]});
}
v.swap(nv);
}
print_int128(ans);
cout<<"\n";
}
return 0;
}
做法 II
不妨更进一步，\gcd 改变是由于新加入的 a_k 不是原 \gcd 的倍数，如果 a_k 是原 \gcd 的倍数显然不用计算，上文的计算式子总为0。只需关注第一个无法被 a_l 整除的数，离 a_l 最近距离为 d=min(a_t \mod a_l, a_l-a_t \mod a_l) ，那么答案至少为 d 且可取到。而对于后续的可以改变前缀 \gcd 的位置来说，首先显然有 g \mid d ，而后续的前缀 \gcd 只会为当前的因子，假设后续前缀 \gcd 变为 h ，则必有 h \mid d，即 h \le d ，而到 h 的距离最大为 \frac h 2 ，有 \frac h 2 \le h \le d ，则不可能有比 d 更大的代价。
因此只需要找到第一个不被 a_l 整除的位置 t ，特别地，如果不存在这样的 t ，那么贡献为0。如果存在那么 t 之后所有右端点都有相同的答案。
代码 II
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+9;
void print_int128(__int128 x){
if(x==0){
cout<<0;
return ;
}
string s;
while(x>0){
s.push_back(char('0'+x%10));
x/=10;
}
reverse(s.begin(),s.end());
cout<<s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin>>T;
while(T--){
int n;
cin>>n;
vector<ll> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<int> st;
__int128 ans=0;
for(int i=1;i<=n;i++){
while(!st.empty()&&a[i]%a[st.back()]!=0){
int l=st.back();
st.pop_back();
ll rem=a[i]%a[l];
ll d=min(rem,a[l]-rem);
ans+=(__int128)((n-i+1)*d);
}
st.push_back(i);
}
print_int128(ans);
cout<<"\n";
}
return 0;
}