xy0v0's Blog

Back

题目#

Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128.

For any array bb of length mm, define f(b)f(b) as the minimum possible value of max⁡(b)−min⁡(b)\max(b) - \min(b) that can be achieved by performing the following operation any number of times:

  • Choose any index 1≤i<m1 \le i \lt m, and do exactly one of the following:
    1. Set bi+1:=bi+1+bib_{i+1} := b_{i+1} + b_i,
    2. Set bi+1:=bi+1−bib_{i+1} := b_{i+1} - b_i.

You are given an array aa of length nn. Your task is to compute the sum of ff over all the subarrays∗^{\text{∗}} of aa. More formally, determine the value of

∑1≤l≤r≤nf([al,al+1,…,ar]).\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]).

∗^{\text{∗}}An array bb is a subarray of an array aa if bb can be obtained from aa 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([b1,b2])f([b_1,b_2]) ,其中 b2b_2 可以加减任意倍数的 b1b_1 ,那么不难发现 f([b1,b2])=min⁡(b2mod  b1,b1−b2mod  b1)f([b_1,b_2])=\min(b_2\mod b_1,b_1-b_2\mod b_1) 。由辗转相除知道 gcd⁡(a,b)=gcd(a,b±a)\gcd(a,b)=gcd(a,b\pm a) ,也就是对于前缀数组进行任意操作都不会改变其 gcd⁡\gcd 。记gr=gcd⁡(b1,b2⋯br)g_r=\gcd(b_1,b_{2} \cdots b_r),那么 bk(k>2)b_k (k>2) 可表示为 bk−1+ngk−1b_{k-1}+ng_{k-1} 。将前缀 gcd⁡\gcd 看做整体,即可化为二元问题,只需要把每个数调整到离其前缀 gcd⁡\gcd 的倍数的最小距离即可,即:

f(b)=maxi=2kmin(bimod  gi−1,gi−1−bimod  gi−1)f(b)=max_{i=2}^k min(b_i\mod g_{i-1},g_{i-1}-b_i \mod g_{i-1})

特别地,有

f([bk])=0f([b_k])=0

对于子数组,记 Gl,r=gcd⁡(al,al+1⋯ar)G_{l,r}=\gcd(a_l,a_{l+1} \cdots a_r) ,子数组的贡献是其右端点从 l+1l+1 到 rr 中的代价最大值,即:

wl,k=min⁡(akmod  Gl,k−1,Gl,k−1−akmod  Gl,k−1)f([al,⋯ ,ar])=maxi=l+1rwl,iw_{l,k}=\min(a_k \mod G_{l,k-1}, G_{l,k-1}-a_k \mod G_{l,k-1}) \\ f([a_l, \cdots,a_r])=max_{i=l+1}^r w_{l,i}

因为 aia_i 仅会受到其前缀的影响,我们不妨固定右端点枚举左端点,定义 curl=f([al,⋯ ,ar])cur_l=f([a_l,\cdots,a_r]) ,设想从 r−1r-1 转移至 rr ,由上文论证,curl=max⁡(curl,wl)cur_l=\max (cur_l,w_l) 。同时容易知道 curr=0cur_r=0 。枚举完右端点后累加所有 curl(l<r)cur_l (l<r) 就是以 rr 为右端点对答案的贡献。

又由于这里 gcd⁡\gcd 的单调性,即扩展端点后前缀 gcd⁡\gcd 不变或者减少到原前缀 gcd⁡\gcd 的一半以上(因为是真因子)。因此不同 gcd⁡\gcd 数量最多是 log⁡A\log A 。因此可将左端点分为若干段,每一段的 Gl,rG_{l,r} 值相同,如果某一段 gcd⁡\gcd 值为 GG ,那么对这段左端点加入 ara_r 的代价都是相同的。

即维护一棵线段树记录 curcur ,支持区间中将所有小于 ww 的数提升至 ww ,并可查询全局和。考虑以下维护方式:

对每个节点维护区间最小值、区间严格次小值、最小值出现次数、区间和。如果 ww 小于等于最小值,那么无需操作;如果 ww 大于最小值同时小于次小值,那么仅需对最小值加到 ww 即可,O(1)O(1) 操作;如果 ww 大于等于严格次小值,那么需要继续递归到子节点。

代码#

做法 II#

不妨更进一步,gcd⁡\gcd 改变是由于新加入的 aka_k 不是原 gcd⁡\gcd 的倍数,如果 aka_k 是原 gcd⁡\gcd 的倍数显然不用计算,上文的计算式子总为0。只需关注第一个无法被 ala_l 整除的数,离 ala_l 最近距离为 d=min(atmod  al,al−atmod  al)d=min(a_t \mod a_l, a_l-a_t \mod a_l) ,那么答案至少为 dd 且可取到。而对于后续的可以改变前缀 gcd⁡\gcd 的位置来说,首先显然有 g∣dg \mid d ,而后续的前缀 gcd⁡\gcd 只会为当前的因子,假设后续前缀 gcd⁡\gcd 变为 hh ,则必有 h∣dh \mid d,即 h≤dh \le d ,而到 hh 的距离最大为 h2\frac h 2 ,有 h2≤h≤d\frac h 2 \le h \le d ,则不可能有比 dd 更大的代价。

因此只需要找到第一个不被 ala_l 整除的位置 tt ,特别地,如果不存在这样的 tt ,那么贡献为0。如果存在那么 tt 之后所有右端点都有相同的答案。

代码 II#