Different GCD Subarray Query

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 714    Accepted Submission(s): 261

Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:
  
  Given an array a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
  
 

Input
There are several tests, process till the end of input.
  
  For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.

You can assume that
  
     1≤N,Q≤100000
    
   1≤ai≤1000000
 

Output
For each query, output the answer in one line.
 

Sample Input
5 3 1 3 4 6 9 3 5 2 5 1 5
 

Sample Output
6 6 6
 【题意】长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种。
【解题方法】fzu月赛原题。固定右端点预处理出 每个点向左延伸 的 不同gcd值，这样的 值不会超过loga 个，然后问题就变成了 问你一段区间内不同 gcd 值有多少，值是很少的 （询问一个区间有多少颜色的题型）。这种类型就随便处理了，bit线段树都可以。
【AC 代码】 
//
//Created by just_sort 2016/9/13 10:57
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
int n,q,a[maxn],ans[maxn],c[maxn],vis[maxn];
vector<pair<int,int> >G[maxn];
struct node{
    int l,r,id;
    bool operator<(const node &rhs){
        return r<rhs.r;
    }
}Q[maxn];
int lowbit(int x){
    return x&(-x);
}
void update(int i,int v){
    while(i<=n){
        c[i] += v;
        i += lowbit(i);
    }
}
int query(int i){
    int ret = 0;
    while(i>0){
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}
int main()
{
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        for(int i=1; i<=n; i++) G[i].clear();
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++){
            int x = a[i];
            int y = i;
            for(int j=0; j<G[i-1].size(); j++){
                int curg = __gcd(x,G[i-1][j].first);
                if(x != curg){
                    G[i].push_back(make_pair(x,y));
                    x = curg;
                    y = G[i-1][j].second;
                }
            }
            G[i].push_back(make_pair(x,y));
        }
        for(int i=1; i<=q; i++){
            scanf("%d%d",&Q[i].l,&Q[i].r);
            Q[i].id = i;
        }
        sort(Q+1,Q+q+1);
        int now = 0;
        for(int i=1; i<=q; i++){
            while(now<Q[i].r){
                now++;
                for(int j=0; j<G[now].size(); j++){
                    int x = G[now][j].first;
                    int y = G[now][j].second;
                    if(vis[x]) update(vis[x],-1);
                    vis[x] = y;
                    update(vis[x],1);
                }
            }
            ans[Q[i].id] = query(now) - query(Q[i].l-1);
        }
        for(int i=1; i<=q; i++){
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}