题解：P9607 [CERC2019] Be Geeks!
缪凌锴_Mathew
·
·
题解
思路
首先，如果只求最大值之和就比较简单。
对于每一个点 x，求出最小的 l，最大的 r，使得：
-
a_{l},a_{l+1},\dots,a_{x-1} <a_x
-
a_{x+1},a_{x+2},\dots,a_r \le a_x
例如下面这个例子:
24 18 20 14 15 30
对于 x=3,a_x=20 来说 l=2,r=5。
所有 $l \le i \le x \le j \le r$ 的区间 $[i,j]$ 的最大值为 $a_x$。
此时对答案的贡献为 $a_x \times \sum_{l \le i \le x \le j \le r} G(i,j)$。
快速求这个 $l,r$，考虑倍增，预处理出每个点向前和向后 $2^k$ 个数的最大值，倍增跳 $l,r$ 到边界。
为什么第一个条件是 $<x$ 而不是 $\le x$ 呢？
**序列中有相等的数会使得区间被重复计算。**
我们向右扩到 $n$，向左扩不超过上一个一样的数，就可以避免使得区间被重复计算。
用 map 维护就能求出上一个一样的数了。
---
现在要求所有 $l \le i \le x \le j \le r$ 的区间 $[i,j]$ 的区间 gcd 的和。
观察这个样例从第一个数开始的前缀 gcd：
```
72 36 48 12 24 18 24 36 66 44 26 34 17 19 51
```
所有前缀 gcd，若有变化，则变化前的 $lstgcd$ 为变化后的 $nxtgcd$ 的倍数。$nxtgcd \le \dfrac{lstgcd}{2}$，因此 gcd 最多有 $\log V$ 种。
得到结论，$x \le p \le r$ 的区间 $[x,p]$ 的 gcd 只有 $\log V$ 种。
同理 $l \le p \le x$ 的区间 $[p,x]$ 的 gcd 只有 $\log V$ 种。
我们只需把两边的这 $\log V$ 种 gcd 求出来，直接暴力 $O(log^{2} V)$ 枚举求答案。
同样，倍增求值，预处理出每个点向前和向后 $2^k$ 个数的 gcd ，每个 gcd 值倍增跳到边界。
复杂度看似还有一个 gcd 的 $O(\log V)$，实际上我们做区间 $[x,i]$ 的 gcd 时可以利用上一次的 gcd ，辗转相除一共 $O(\log V)$ 次，均摊下来每次 gcd 的复杂度为 $O(1)$。
总复杂度 $O(n \log^{2} V)$。
## 代码
```cpp
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
const int MAXM=25;//log n
const int M=20;
const int MAXK=35;//log V
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
int gcd(int a,int b){
if(!b){
return a;
}
return gcd(b,a%b);
}
int n,ans=0;
int a[MAXN];
int maxl[MAXN][MAXM],maxr[MAXN][MAXM];//i向左、向右2^k个数的最大值
int gcdl[MAXN][MAXM],gcdr[MAXN][MAXM];//i向左、向右2^k个数的gcd
map <int,int> mp;
struct node{//每一个最大公因数的范围，数值
int ql,qr,val;
}L[MAXK],R[MAXK];
int cntl,cntr;//左。右的最大公因数的数值个数（<logV）
void work(int x){
int l=x,r=x;
int lim=mp[a[x]];//上一个一样的数（没有则为0）
for(int i=M;i>=0;i--)//倍增跳l和r
{
if(l-(1<<i)>lim&&maxl[l-1][i]<=a[x]){
l-=(1<<i);
}
if(r+(1<<i)<=n&&maxr[r+1][i]<=a[x]){
r+=(1<<i);
}
}
cntl=0;
cntr=0;
int Gcd=a[x],p=x;//当前最大公因数的数值，当前位置
while(1)
{
int lst=p;
for(int i=M;i>=0;i--)
{
if(p-(1<<i)>=l&&gcdl[p-1][i]%Gcd==0){
p-=(1<<i);
}
}
cntl++;
L[cntl]=(node){p,lst,Gcd};
if(p==l){
break;
}
p--;
Gcd=gcd(Gcd,a[p]);
}
Gcd=a[x];
p=x;
while(1)
{
int lst=p;
for(int i=M;i>=0;i--)
{
if(p+(1<<i)<=r&&gcdr[p+1][i]%Gcd==0){
p+=(1<<i);
}
}
cntr++;
R[cntr]=(node){lst,p,Gcd};
if(p==r){
break;
}
p++;
Gcd=gcd(Gcd,a[p]);
}
int res=0;
//暴力统计答案
for(int i=1;i<=cntl;i++)
{
int lst=L[i].val;//优化gcd
for(int j=1;j<=cntr;j++)
{
int lenl=L[i].qr-L[i].ql+1;
int lenr=R[j].qr-R[j].ql+1;
res+=1ll*lenl*lenr%mod*gcd(lst,R[j].val)%mod;
res%=mod;
}
}
ans+=1ll*res*a[x]%mod;
ans%=mod;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxl[i][0]=a[i];
maxr[i][0]=a[i];
gcdl[i][0]=a[i];
gcdr[i][0]=a[i];
}
for(int i=1;i<=M;i++)//预处理
{
int len=(1<<(i-1));
for(int j=1;j<=n;j++)
{
maxl[j][i]=maxl[j][i-1];
maxr[j][i]=maxr[j][i-1];
gcdl[j][i]=gcdl[j][i-1];
gcdr[j][i]=gcdr[j][i-1];
}
for(int j=1;j+len<=n;j++)
{
maxr[j][i]=max(maxr[j][i],maxr[j+len][i-1]);
gcdr[j][i]=gcd(gcdr[j][i],gcdr[j+len][i-1]);
}
for(int j=len+1;j<=n;j++)
{
maxl[j][i]=max(maxl[j][i],maxl[j-len][i-1]);
gcdl[j][i]=gcd(gcdl[j][i],gcdl[j-len][i-1]);
}
}
for(int i=1;i<=n;i++)
{
work(i);
mp[a[i]]=i;
}
printf("%d\n",ans);
return 0;
}
```
#### update 2023.10.8 改正一个错误，感谢 [@Sunny郭](https://www.luogu.com.cn/user/360547) 指出。
#### update 2023.10.25 改正一个复杂度分析的错误，感谢 [@VioletIsMyLove](https://www.luogu.com.cn/user/188879) 指出。