比赛的时候没搞定怎么维护gcd求和的问题，赛后看了题解也感觉不是很懂，问了逊神，一句话提示了我：区间gcd就是一个序列而已！！！然后我就知道自己是个傻逼了。区间维护，很容易想到用一个RMQ搞定，用莫队写的话，关键在如何维护答案，[L,R] - > [L,R+1]这段中，多出来了什么东西？区间[L、L+1....R+1,R+1]这所有区间的gcd，这个题还有一个关键就是以R为左端点或者右端点的所有区间的gcd值最多有o(log(a[i]))种，那么我们用莫队维护的时候，每一次暴力的复杂度就是o(log(a[i]))。
我们发现现在莫队的复杂度已经到了n*sqrt(n)*log(a[i])了，再加操作就会T了（其实我也不知道会不会，因为我直接离线写的，只是感觉会T）。但是我们剩下来还有一个问题没有解决。num[i] 在 [L,R]这段区间的每个gcd的值是多少？并且每个gcd值对应了多少段区间。这个时候我们很容易想到2分，因为随着区间长度的增加，gcd值是一个不升的过程。RMQ求区间gcd的复杂度就是o(n*logn*logn)。RMQ完了预处理出每个i左边每个gcd，右边每个gcd对应的位置需要o(n*logn*logn)（之所以多一个logn，因为二分的时候需要）。
当然这道题题解给出的使用树状数组维护。然而个人比较喜欢暴力！！！
感觉这道题很难讲清楚，还是自己敲一遍比较有感觉。然后这道题让我发现了我一直以来写莫队的一个错误的地方，也是我之前补题的时候那道题一直没有AC的原因，在代码里面mark出来吧，还是。下面是AC代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll long long
#define FOR(i,x,y) for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define N 11000
using namespace std;
const int M = (int)sqrt(N+0.5);
int num[N],n,Q;
int l[N][50],r[N][50],lp[N][50],rp[N][50],lc[N],rc[N],lv[N][50],rv[N][50];
ll ANS[N];
int GCD(int a,int b){
if(b > a) {int tem = a;a = b;b = tem;}
return b == 0 ? a : GCD(b,a%b);
}
void RMQ(){
FOR(i,0,n){
l[i][0] = num[i];
r[i][0] = num[i];
}
int bit = (int)log2(n*1.0);
FOR(i,1,bit+1){
FOR(j,0,n){
if(j + (1<<i) > n) break;
r[j][i] = GCD(r[j][i-1],r[j+(1<<(i-1))][i-1]);
}
}
FOR(i,1,bit+1){
IFOR(j,n-1,-1){
if(j - (1<<i) < -1) break;
l[j][i] = GCD(l[j][i-1],l[j-(1<<(i-1))][i-1]);
}
}
}
void init(){
RMQ();
FOR(i,0,n){
lc[i] = rc[i] = 0;
int bit1 = (int)log2(1.0*(n-i));
int bit2 = (int)log2(1.0*(i+1));
int flag1 = GCD(r[i][bit1],r[n-(1<<bit1)][bit1]);
int flag2 = GCD(l[i][bit2],r[0][bit2]);
int tem = num[i],pos = i;
while(1){
int L = pos, R = n-1;
if(tem == flag1){
rv[i][rc[i]] = tem;
rp[i][rc[i]++] = n;
break;
}
while(L < R){
int mid = (L+R) >> 1;
int bit = (int)log2(mid-i+1.0);
int t = GCD(r[i][bit],l[mid][bit]);
if(t == tem) L = mid+1;
else R = mid;
}
rv[i][rc[i]] = tem;
tem = GCD(tem,num[L]);
rp[i][rc[i]++] = L;
pos = L;
}
tem = num[i];
pos = i;
while(1){
int L = 0, R = pos;
if(tem == flag2){
lv[i][lc[i]] = tem;
lp[i][lc[i]++] = -1;
break;
}
while(L < R){
int mid = (L+R+1) >> 1;
int bit = (int)log2(i-mid+1.0);
int t = GCD(l[i][bit],r[mid][bit]);
if(t == tem) R = mid-1;
else L = mid;
}
lv[i][lc[i]] = tem;
tem = GCD(tem,num[R]);
lp[i][lc[i]++] = R;
pos = R;
}
}
}
struct Commends{
int lx,rx;
int id;
bool operator < (const Commends& rhs) const{
if(lx/M == rhs.lx/M) return (rx < rhs.rx); ///这个地方一定不能写成rx/M < rhs.rx/M （话说如果写成这样了，为什么不是t，而是wa？有没有大神可以给个解释？）
return (lx/M < rhs.lx/M);
}
}cmd[N];
void MO(){
int L = 0,R = -1;
ll ans = 0;
FOR(j,0,Q){
while(R < cmd[j].rx){
R ++;
int pos = R;
ll tem = 0;
FOR(i,0,lc[R]){
if(lp[R][i] < L){
tem += (ll)lv[R][i]*(ll)(pos-L+1);
break;
}
tem += (ll)lv[R][i]*(ll)(pos - lp[R][i]);
pos = lp[R][i];
}
ans += tem;
}
while(R > cmd[j].rx){
int pos = R;
ll tem = 0;
FOR(i,0,lc[R]){
if(lp[R][i] < L){
tem += (ll)lv[R][i]*(ll)(pos-L+1);
break;
}
tem += (ll)lv[R][i]*(ll)(pos - lp[R][i]);
pos = lp[R][i];
}
ans -= tem;
R --;
}
while(L < cmd[j].lx){
int pos = L;
ll tem = 0;
FOR(i,0,rc[L]){
if(rp[L][i] > R){
tem += (ll)rv[L][i]*(ll)(R-pos+1);
break;
}
tem += (ll)rv[L][i]*(ll)(rp[L][i] - pos);
pos = rp[L][i];
}
ans -= tem;
L ++;
}
while(L > cmd[j].lx){
L --;
int pos = L;
ll tem = 0;
FOR(i,0,rc[L]){
if(rp[L][i] > R){
tem += (ll)rv[L][i]*(ll)(R-pos+1);
break;
}
tem += (ll)rv[L][i]*(ll)(rp[L][i] - pos);
pos = rp[L][i];
}
ans += tem;
}
ANS[cmd[j].id] = ans;
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
FOR(i,0,n) scanf("%d",&num[i]);
init();
scanf("%d",&Q);
//M = (int) sqrt(n+0.5);
int u,v;
FOR(i,0,Q){
scanf("%d%d",&u,&v);
cmd[i].lx = u-1;
cmd[i].rx = v-1;
cmd[i].id = i;
}
sort(cmd,cmd+Q);
MO();
FOR(i,0,Q){
printf("%I64d
",ANS[i]);
}
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。