本文共 2228 字，大约阅读时间需要 7 分钟。
知道对于一个数列，如果以x为左(右)端点，往右走，则最多会有log(a[x])个不同的gcd，并且有递减性
所以会分成log段，每一段的gcd相同
那我们可以预处理出对于每一个位置，以这个位置为左端点和右端点的时候，分别产生的gcd的值和分界处
那么这道题就可以用莫队算法了，O(n * sqrt(n) * logn)
标程是用线段树
代码：
//File Name: hdu5381.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年10月24日 星期一 11时36分49秒#include #include #include #include #include #include #include #include #include #define LL long long#define pii pair #define fir first#define sec second#define mp make_pairusing namespace std;const int MAXN = 10000 + 10;int bel[MAXN],a[MAXN],cur_l,cur_r,tot;LL ans[MAXN],cur_ans;vector tol[MAXN],tor[MAXN];struct Query{ int l,r,t; bool operator < (const Query & x) const{ if(bel[l] == bel[x.l]) return r < x.r; return bel[l] < bel[x.l]; }}que[MAXN];int gcd(int x,int y){ return y == 0 ? x : gcd(y, x % y);}void init(int n){ pii now; for(int i=1;i<=n;i++){ tol[i].clear(); tol[i].push_back(mp(i,a[i])); if(i == 1) continue; int tot = 0,len = tol[i-1].size(); for(int j=0;j 0;i--){ tor[i].clear(); tor[i].push_back(mp(i,a[i])); if(i == n) continue; int tot = 0,len = tor[i+1].size(); for(int j=0;j now.fir){ res += (LL)(now.fir - pre + 1) * now.sec; pre = now.fir + 1; } else{ res += (LL)(r - pre + 1) * now.sec; break; } } return res;}void mover(int to){ while(cur_r < to){ cur_r++; cur_ans += gettol(cur_l,cur_r); } while(cur_r > to){ cur_ans -= gettol(cur_l,cur_r); cur_r--; }}void movel(int to){ while(cur_l < to){ cur_ans -= gettor(cur_l,cur_r); cur_l++; } while(cur_l > to){ cur_l--; cur_ans += gettor(cur_l,cur_r); }}void solve(int n,int q){ init(n); int block = (int)sqrt(n + 0.5); for(int i=1;i<=n;i++) bel[i] = (n - 1) / block + 1; sort(que+1,que+q+1); cur_l = cur_r = 1,cur_ans = a[1]; for(int i=1;i<=q;i++){ mover(que[i].r); movel(que[i].l); ans[que[i].t] = cur_ans; } for(int i=1;i<=q;i++) printf("%I64d\n",ans[i]);}int main(){ int t,n,q; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a + i); scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%d %d",&que[i].l,&que[i].r); que[i].t = i; } solve(n,q); } return 0;}
转载于:https://www.cnblogs.com/-maybe/p/6000308.html
