G. Summmon
题意
给定数组a。对任意一个子数组b，可以执行任意次操作：
选择 1 <= i < m b[i + 1] := b[i + 1] + b[i] 或者 b[i + 1] := b[i + 1] - b[i]记f(b)为经过若干次操作后，max(b) - min(b)能达到的最小值。
要求计算所有子数组的f之和：
sum f(a[l ... r])答案可能超过long long。
先看操作本质
第一个元素永远不会被改变，因为没有位置能操作到它。
对于一个子数组：
b = [b1, b2, ..., bm]设当前要处理第i个数。它前面的数是：
b1, b2, ..., b[i - 1]通过操作，第i个数可以加上或减去前面这些数凑出来的整数线性组合。根据 gcd 的性质，它最终能变成的数恰好满足：
新值 ≡ 原值 (mod gcd(b1, b2, ..., b[i - 1]))也就是说：
第 i 个数能怎么调整，只由它前面所有数的 gcd 决定。这是整道题最重要的观察。
核心结论
考虑一个子数组：
b = [b1, b2, ..., bm]令：
x = b1从左往右找第一个不能被x整除的位置p：
b[p] % x != 0如果不存在这样的p，那么：
f(b) = 0如果存在这样的p，令：
r = b[p] % x那么：
f(b) = min(r, x - r)一句话总结：
一个子数组的贡献，只看首元素和后面第一个不能被首元素整除的数。为什么只看第一个不整除的位置
还是设x = b1。
情况 1：后面全是 x 的倍数
如果：
b2, b3, ..., bm全部都是x的倍数，那么可以从左到右把每个元素都调整成x。
例如：
[6, 12, 24] -> [6, 6, 6]所以此时：
f(b) = 0情况 2：出现第一个不是 x 倍数的数
设p是第一个满足b[p] % x != 0的位置。
因为p前面的数都是x的倍数，所以在处理b[p]之前，前缀 gcd 仍然是x。
因此b[p]只能变成：
b[p] + k * x也就是所有和b[p]模x同余的数。
令：
r = b[p] % x那么b[p]离x最近的可能位置，距离就是：
min(r, x - r)记这个值为w。
所以答案至少是w。
另一方面，答案确实可以做到w：
- 如果
r <= x - r，把b[p]放到x + r，区间可以是[x, x + r]。 - 如果
r > x - r，把b[p]放到r，区间可以是[r, x]。
这个区间长度正好是w。
处理完b[p]后，前缀 gcd 会变成：
g = gcd(x, b[p])因为g同时整除x和b[p]，所以它也整除r和x - r，从而整除w。
于是：
g <= w长度为w的连续整数区间里，至少能覆盖模g的所有余数。后面的前缀 gcd 只会继续变成g的因子，所以后面的每个元素都可以被调整进这个区间，不会让答案继续变大。
因此：
f(b) = w = min(b[p] % x, x - b[p] % x)如何统计所有子数组
固定左端点l。
令：
x = a[l]找到最小的p > l，满足：
a[p] % x != 0如果不存在这样的p，那么所有以l开头的子数组贡献都是0。
如果存在这样的p，令：
w = min(a[p] % x, x - a[p] % x)那么：
- 右端点
r < p时，子数组a[l ... r]后面全是x的倍数，贡献是0。 - 右端点
r >= p时，第一个不整除位置都是p，贡献都是w。
这样的右端点有：
n - p + 1个。
所以左端点l对总答案的贡献是：
w * (n - p + 1)怎么快速找到 p
我们需要对每个l找第一个不能被a[l]整除的位置。
考虑区间[l + 1, mid]。
这段区间里的所有数都能被a[l]整除，等价于：
gcd(a[l + 1], ..., a[mid]) % a[l] == 0所以可以：
- 建一个 gcd 稀疏表，支持
O(1)查询区间 gcd。 - 对每个左端点
l，二分第一个不满足条件的位置p。
为什么可以二分？
如果[l + 1, mid]已经包含了一个不能被a[l]整除的数，那么这段区间的 gcd 也不可能再被a[l]整除。所以条件具有单调性。
例子
数组：
[6, 4, 8]按左端点统计：
| 左端点 l | x = a[l] | 第一个不被 x 整除的位置 p | w | 贡献 |
|---|---|---|---|---|
| 1 | 6 | p = 2, a[p] = 4 | min(4, 2) = 2 | 2 * 2 = 4 |
| 2 | 4 | 不存在，因为 8 能被 4 整除 | 0 | 0 |
| 3 | 8 | 不存在 | 0 | 0 |
总答案：
4复杂度
设数组长度为n。
| 内容 | 复杂度 |
|---|---|
| 建 gcd 稀疏表 | O(n log n) |
| 每个左端点二分 | O(log n) |
| 总时间复杂度 | O(n log n) |
| 空间复杂度 | O(n log n) |
所有测试用例的n之和不超过2 * 10^5，可以通过。
C++ 代码
下面的代码没有依赖__int128或 Boost。答案用一个很小的大整数维护，只需要支持加上一个long long和输出。
#include<bits/stdc++.h>usingnamespacestd;usingint64=longlong;structBigInt{staticconstintBASE=1000000000;vector<int>d;voidadd(longlongx){inti=0;while(x>0){if(i==(int)d.size())d.push_back(0);longlongcur=(longlong)d[i]+x%BASE;d[i]=int(cur%BASE);x=x/BASE+cur/BASE;i++;}}stringstr()const{if(d.empty())return"0";string res=to_string(d.back());for(inti=(int)d.size()-2;i>=0;i--){string part=to_string(d[i]);res+=string(9-part.size(),'0')+part;}returnres;}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<int64>a(n+1);for(inti=1;i<=n;i++){cin>>a[i];}intK=__lg(n)+1;vector<vector<int64>>st(K,vector<int64>(n+1));for(inti=1;i<=n;i++){st[0][i]=a[i];}for(intk=1;k<K;k++){intlen=1<<k;for(inti=1;i+len-1<=n;i++){st[k][i]=gcd(st[k-1][i],st[k-1][i+(len>>1)]);}}autorange_gcd=[&](intl,intr)->int64{intlen=r-l+1;intk=__lg(len);returngcd(st[k][l],st[k][r-(1<<k)+1]);};BigInt ans;for(intl=1;l<=n;l++){if(l==n)continue;int64 x=a[l];intpos=n+1;intlow=l+1;inthigh=n;while(low<=high){intmid=(low+high)/2;int64 g=range_gcd(l+1,mid);if(g%x==0){low=mid+1;}else{pos=mid;high=mid-1;}}if(pos<=n){int64 r=a[pos]%x;int64 w=min(r,x-r);ans.add(w*1LL*(n-pos+1));}}cout<<ans.str()<<'\n';}return0;}小结
这题最关键的一步是不要模拟操作，而是把操作转成 gcd 和同余：
后面的数只能在某个 gcd 模意义下移动。再利用首元素固定这一点，可以进一步发现：
每个子数组只由第一个不被首元素整除的位置决定贡献。于是问题就变成了：
对每个左端点，快速找到第一个不整除的位置。用 gcd 稀疏表加二分即可完成。
