题目#
Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128.
For any array of length , define as the minimum possible value of that can be achieved by performing the following operation any number of times:
- Choose any index , and do exactly one of the following:
- Set ,
- Set .
You are given an array of length . Your task is to compute the sum of over all the subarrays of . More formally, determine the value of
An array is a subarray of an array if can be obtained from 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.
做法#
先考虑二元的做法即 ,其中 可以加减任意倍数的 ,那么不难发现 。由辗转相除知道 ,也就是对于前缀数组进行任意操作都不会改变其 。记,那么 可表示为 。将前缀 看做整体,即可化为二元问题,只需要把每个数调整到离其前缀 的倍数的最小距离即可,即:
特别地,有
对于子数组,记 ,子数组的贡献是其右端点从 到 中的代价最大值,即:
因为 仅会受到其前缀的影响,我们不妨固定右端点枚举左端点,定义 ,设想从 转移至 ,由上文论证, 。同时容易知道 。枚举完右端点后累加所有 就是以 为右端点对答案的贡献。
又由于这里 的单调性,即扩展端点后前缀 不变或者减少到原前缀 的一半以上(因为是真因子)。因此不同 数量最多是 。因此可将左端点分为若干段,每一段的 值相同,如果某一段 值为 ,那么对这段左端点加入 的代价都是相同的。
即维护一棵线段树记录 ,支持区间中将所有小于 的数提升至 ,并可查询全局和。考虑以下维护方式:
对每个节点维护区间最小值、区间严格次小值、最小值出现次数、区间和。如果 小于等于最小值,那么无需操作;如果 大于最小值同时小于次小值,那么仅需对最小值加到 即可, 操作;如果 大于等于严格次小值,那么需要继续递归到子节点。
代码#
#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;
}cpp做法 II#
不妨更进一步, 改变是由于新加入的 不是原 的倍数,如果 是原 的倍数显然不用计算,上文的计算式子总为0。只需关注第一个无法被 整除的数,离 最近距离为 ,那么答案至少为 且可取到。而对于后续的可以改变前缀 的位置来说,首先显然有 ,而后续的前缀 只会为当前的因子,假设后续前缀 变为 ,则必有 ,即 ,而到 的距离最大为 ,有 ,则不可能有比 更大的代价。
因此只需要找到第一个不被 整除的位置 ,特别地,如果不存在这样的 ,那么贡献为0。如果存在那么 之后所有右端点都有相同的答案。
代码 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;
}cpp