1.题目描述：点击打开链接
2.解题思路：本题利用莫队算法解决。由于是第一次学习这个算法，因此研究了比较长的一段时间才弄懂。首先，莫队算法解决的问题是无修改的离线区间查询问题。该算法实际上是由曼哈顿距离最小生成树演变来的，由于要处理m个区间，可以将这m个区间看做二维平面上的点，那么处理这m个区间就等价于让这m点连通，且总的转移代价最小。这其实就是一个曼哈顿距离最小生成树问题。
经典的曼哈顿距离最小生成树的时间复杂度是O(NlogN)，莫队算法的时间复杂度是O(N^1.5)。不过本题还有一个地方，就是区间怎么处理。因为GCD相同的区间是可以合并的，因此不同的区间个数实际上是log级别的，一共有左右N个区间要处理，复杂度是O(NlogN)。下面用一个简单的例子来说明一下区间合并。
比如，数组是2,3,3,6,8,16，下标从1开始，下面的[i,j]->g表示a[i]到a[j]所有数到左端点的区间的GCD都是g。
a[1]=2: [1,1]->2, [2,6]->1
a[2]=3: [2,4]->3, [5,6]->1
a[3]=3: [3,4]->3, [5,6]->1
a[4]=6: [4,4]->4, [5,6]->2
a[5]=8: [5,6]->8
a[6]=16: [6,6]->16
从上面的例子中可以发现，以i为左端点构成的所有GCD值不等的区间实际上非常少。
处理完区间，接下来就是套用莫队算法，，首先对M个查询区间进行分块排序，block=sqrt(n)，首先对左端点进行排序，若相等，再对右端点排序。这样排序后可以保证总的转移代价是最小的，接下来就是进行区间转移了，举一个简单的例子来说明如何转移。
假如我们已经计算出了[L1,R1]的结果是res，下一个要计算的区间是[L2,R2]，且L1<L2，R1<R2。
那么我们画图后发现，res需要减去从L1变化到L2-1的所有结果，同时要加上从R1变化到R2的所有结果。这样就得到了新的res。
3.代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<algorithm>#include<cassert>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<cctype>#include<functional>using namespace std;#define me(s) memset(s,0,sizeof(s))typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;typedef pair <int, int> P;const int N=10000+5;int n,m;int block;int a[N];ll ans[N];struct Node{int L,R;int id;bool operator<(const Node&rhs)const{if(L/block==rhs.L/block)return R<rhs.R;return L/block<rhs.L/block;}}q[N];int gcd(int a,int b){return !b?a:gcd(b,a%b);}struct He{int idx;ll g;};vector<He>vl[N],vr[N];void preDeal() //预处理所有以i为左端点的区间，他们的右端点都存放到vr[i]中；同理处理所有以i为右端点的区间，它们的左端点都存放到vl[i]中{for(int i=1;i<=n;i++)//i从左到右变化，计算所有的vl[i]（此时i作为一个固定的右端点）{if(i==1)vl[i].push_back(He{i,a[i]});//第一个区间，只有自身else{int curg=a[i];//当前的GCD值int L=i;//第一个左端点for(auto&it:vl[i-1])//每次都以i-1为右端点的区间开始扩展，得到以i为右端点的区间{int g=gcd(it.g,curg);if(g!=curg)//g!=curg说明以i-1为右端点的这个区间不能和加入a[i]后得到的新区间合并，那么单独保存新区间。若相等则试图继续扩展左端点Lvl[i].push_back(He{L,curg});curg=g,L=it.idx;//更新curg和L值，得到新的左端点L 和 以L为左端点，i为右端点的区间的GCD值}vl[i].push_back(He{L,curg});//最后一个区间}}for(int i=n;i>=1;i–)//用同样的方法处理以i为左端点的所有区间{if(i==n)vr[i].push_back(He{i,a[i]});else{int curg=a[i];int R=i;for(auto&it:vr[i+1]){int g=gcd(it.g,curg);if(g!=curg)vr[i].push_back(He{R,curg});curg=g,R=it.idx;}vr[i].push_back(He{R,curg});}}}ll calc(int type,int L,int R)//计算区间[L,R]的结果{ll res=0;if(!type){int tr=R; //当前的右端点for(auto&it:vl[R])if(it.idx>=L)//如果当前区间的左端点>=L,则当前区间为[it.idx,tr]{res+=(tr-it.idx+1)*it.g; //这里其实用到了GCD值的传递性：如果L<L1<R,gcd([L,R])=g1,gcd([L1,R])=g2(g2≥g1)，那么必有gcd([L,L1-1])=g1tr=it.idx-1; //更新右端点}else//如果当前区间的左端点<L，则应该被算入的区间为[L,tr]，由于它是最后一个区间了，因此break{res+=(tr-L+1)*it.g;break;}}else//原理同上{int tl=L;for(auto&it:vr[L])if(it.idx<=R){res+=(it.idx-tl+1)*it.g;tl=it.idx+1;}else{res+=(R-tl+1)*it.g;break;}}return res;}void solve(){for(int i=1;i<=n;i++)vl[i].clear(),vr[i].clear();block=sqrt(n);//块数sort(q,q+m);preDeal();int L=1,R=0;从(1,0)点开始转移，此时res=0ll res=0;for(int i=0;i<m;i++){while(R<q[i].R){R++;//向右右端点，然后计算[L,R]区间的结果，累加给resres+=calc(0,L,R);}while(R>q[i].R)//向左移动右端点{res-=calc(0,L,R);R–;}while(L>q[i].L){L–;res+=calc(1,L,R);}while(L<q[i].L){res-=calc(1,L,R);L++;}ans[q[i].id]=res;//转移完毕。注意，res,L,R都不要清零}for(int i=0;i<m;i++)printf("%I64d\n",ans[i]);}int main(){int T;scanf("%d",&T);while(T–){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(int i=0;i<m;i++){scanf("%d%d",&q[i].L,&q[i].R);q[i].id=i;}solve();}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
孤独是为了孤独背后的解脱，孤独的过程，就是一个寻找真爱的过程。
