[CF] 474 F. Ant colony

区间重复不会影响GCD，ST表当然是支持的啦，常数这么小。

学到了三个东西：

1.lower_bound返回的是大于等于的位置，要判是否不存在(end())和是否超出所求[x,y]范围。

2.ST表更新时存在一个i+(1<<j-1)的下标，存在极大越界隐患，以前数组开的大就无所谓，讲道理边界是要判的。

3.及时存代码，又蓝屏了qwq

#include<iostream>

#include<cstdio>

#include<vector>

#include<map>

using namespace std;

inline int rd(){

  int ret=,f=;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-:;

  while(isdigit(c))ret=ret*+c-'',c=getchar();

  return ret*f;

}

int LOG2 (unsigned int x) {

   static const int log_2[] = {

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

   };

   int l = -;

   while (x >= ) { l += ; x >>= ; }

   return l + log_2[x];

}

const int MAXN=;

int n,m;

int a[MAXN];

int f[MAXN][];

int id;

map<int,int> M;

vector<int> V[MAXN];

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int query(int x,int y){

  if(x==y) return f[x][];

  int len=LOG2(y-x+);

  return gcd(f[x][len],f[y-(<<len)+][len]);

}

int main(){

  n=rd();

  for(int i=;i<=n;i++) f[i][]=a[i]=rd();

  for(int i=;i<=n;i++){

    if(!M.count(a[i])) M[a[i]]=++id;

    V[M[a[i]]].push_back(i);

  }

  for(int j=;(<<j)<=n;j++)

    for(int i=;i+(<<(j-))<=n;i++)

      f[i][j]=gcd(f[i][j-],f[i+(<<(j-))][j-]);

  m=rd();

  int x,y,g,tmp,l,r,ans;

  for(int i=;i<=m;i++){

    x=rd();y=rd();

    g=query(x,y);

    tmp=M[g];

    r=lower_bound(V[tmp].begin(),V[tmp].end(),y)-V[tmp].begin();

    l=lower_bound(V[tmp].begin(),V[tmp].end(),x)-V[tmp].begin();

    if(r+V[tmp].begin()==V[tmp].end()||V[tmp][r]>y) r--;

    cout<<y-x+-(r-l+)<<endl;

  }

  return ;

}