学校模拟赛的某道题让我联想到了这道题……
先讲一下我的野鸡做法。
首先考虑分治，对于左右端点都在 ([L,R]) 中的区间我们将其分成三类：完全包含于 ([L,mid]) 的区间，完全包含于 ([mid+1,R]) 的区间，和跨过中间点的区间。前两种我们只需进一步递归 ([L,mid]) 和 ([mid+1,R]) 即可求解出答案，比较麻烦的是第三种。我们考虑先扫一遍预处理出 (F_i=gcd(a_i,a_{i+1},cdots,a_{mid}))，以及 (G_i=gcd(a_{mid+1},a_{mid+2},cdots,a_{i}))，那么对于一个满足 (lin[L,mid],rin[mid+1,R])，其权值 (W(l,r)=(r-l+1)·gcd(F_l,G_r))，直接枚举依然不可做，不过注意到 (F_i,G_i) 不同数的种类不超过 (log a_i) 种，因此考虑对 (F_i,G_i) 相同的值，我们只保留其最靠左（右）的一个，然后暴力枚举更新答案即可。这个时间复杂度的计算要动点脑筋，乍一看是 (nlog^3n) 的（包括我一开始做这道题时也这么认为），但今天才发现它其实是 2log 的，不妨设 (n) 为 (2) 的整数次幂，(n) 不是 (2) 的整数次幂的情况与其最近的 (2) 的整数次幂效率上显然只是常数的差别。首先求 (F_i,G_i) 肯定是 2log 的，区间长度 1log + gcd 1log，比较棘手的是暴力枚举复杂度是什么，若区间长度 (<log n)，那么枚举次数的上界肯定是区间长度的平方，(T_1=sumlimits_{i=2^k,kinmathbb{Z},ilelog n}dfrac{n}{i}·i^2=sumlimits_{i=2^k,kinmathbb{Z},ilelog n}ni)，又 (i) 为 (2) 的整数次幂，根据等比数列求和公式，后面那东西是 (mathcal O(nlog n)) 的，若区间长度 (>log n)，那么对于长度为 (i) 的区间，单次枚举复杂度 (log^2n)，而这样的区间最多 (dfrac{n}{i}) 个，因此复杂度就是 (T_2=log^2nsumlimits_{i>log n,i=2^k,kinmathbb{Z}}dfrac{n}{i})，还是根据等比数列求和公式，后面的 (sum) 里的东西是 (mathcal O(dfrac{n}{log n})) 级别的，因此总枚举次数是 (mathcal O(nlog n)) 的，再加上 gcd 的 (mathcal O(log n))，总复杂度就是 (mathcal O(nlog^2n))
const int MAXN=1e5;
ll gcd(ll x,ll y){return (!y)?x:gcd(y,x%y);}
int n;ll a[MAXN+5],ans=0,pre[MAXN+5],suf[MAXN+5];
void solve(int l,int r){
if(l==r) return chkmax(ans,a[l]),void();
int mid=l+r>>1;solve(l,mid);solve(mid+1,r);
for(int i=l;i<=r;i++) pre[i]=suf[i]=0;
for(int i=mid;i>=l;i--) suf[i]=gcd(suf[i+1],a[i]);
for(int i=mid+1;i<=r;i++) pre[i]=gcd(pre[i-1],a[i]);
vector<pair<ll,int> > v1,v2;
for(int i=l;i<=mid;i++) if(i==l||(suf[i]^suf[i-1])) v1.pb(mp(suf[i],mid-i+1));
for(int i=mid+1;i<=r;i++) if(i==r||(pre[i]^pre[i+1])) v2.pb(mp(pre[i],i-mid));
for(int i=0;i<v1.size();i++) for(int j=0;j<v2.size();j++) chkmax(ans,gcd(v1[i].fi,v2[j].fi)*(v1[i].se+v2[j].se));
}
int main(){
scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
solve(1,n);printf("%lld
",ans);
return 0;
}
事实上有一个非常 simple 的复杂度也是 2log 的做法，我们固定左端点，那么随着右端点的变化，(gcd) 最多变化 (log a_i) 次，那么我们可以二分找出这 (log a_i) 次的断点，然后每次取断点左边的点更新答案即可，求区间 (gcd) 可以 ST 表，复杂度 (nlog^2n)。
最后稍微总结一下这道题带给我们的启示：
- 碰到像区间 gcd 这样固定住左端点，随着右端点的增大，区间权值变化量很小（一般 (log n) 级别）的权值函数，可以考虑二分权值变化的位置，这样即可将 ([1,r]) 拆分成一段段区间，每段区间内所有 (l) 都有 ([l,r]) 权值相同，这样就比较好维护答案（我记得之前某场模拟赛还有这样一个问题：给定长度为 (n) 的数列，要你将序列分成 (k) 段，求每段 bitwise or 值之和的最大值，当时一点思路都没有，现在知道了这个技巧，学了 wqs 二分，不就得心应手了？）有时还可以利用排序后差分数组的 gcd 与原数组差分数组的 gcd 相同这一性质进行转化，并运用区间 gcd 的性质维护，具体应用就是校内模拟赛那道题，隐私起见就不把题面亮在这里了（
- 碰到求满足条件的区间个数，或者要你求某个区间权值最大值，一般这个权值还与区间长度有关，可以考虑分治求解（虽然这题分治与不分治效率差别并不是太大）