[原创]HDU 5869 Different GCD Subarray Query [区间gcd预处理+离线]【数据结构】

# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 100000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
inline int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
/***********************************************************************/
int sum[N];
# define lowbit(x) (x&-x)
void update(int index,int val){
    for(int i=index;i<N;i+=lowbit(i)) sum[i]+=val;
}
int getSum(int index){
    int ans = 0;
    for(int i=index;i;i-=lowbit(i)) ans += sum[i];
    return ans;
}
vector<pair<int,int> >E[N];
int a[N],ans[N];
struct node {
    int l,r,id;
    bool operator <(const node &p) const{
        //if(r==p.r) return l<p.l;
        return r<p.r;
    }
}q[N];
map<int,int>vis;
int main(){
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<=m;++i) scanf("%d %d",&q[i].l,&q[i].r),q[i].id=i,ans[i]=0;
        sort(q+1,q+m+1);

        for(int i=0;i<=n;++i)E[i].clear();
        for(int i=1;i<=n;++i){
            int x=a[i];
            int y=i;
            for(int j=0;j<E[i-1].size();++j){
                int res=gcd(x,E[i-1][j].first);
                if(x!=res){
                    E[i].pb(mp(x,y));
                    x=res;
                    y=E[i-1][j].second;
                }
            }
            E[i].pb(mp(x,y));
        }

        vis.clear();
        for(int R=0,i=1;i<=m;++i){
            while(R < q[i].r){
                R++;
                for(int j=0;j<E[R].size();++j) {
                    int res=E[R][j].first;
                    int ids=E[R][j].second;
                    if(vis[res]) update(vis[res],-1);
                    vis[res] = ids;
                    update(vis[res],1);
                }
            }

            ans[q[i].id] = getSum(R) - getSum(q[i].l-1);
        }

        for(int i=1;i<=m;++i)      printf("%d\n",ans[i]);
    }
    return 0;
}