题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5869
赛场上用树状数组预处理后一直超时，一直到比赛结束也没过去。后来在大神指导下用RMQ过掉。
AC 代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=1e6+6;
template <class T>
inline void read(T &x)
{
char c=getchar();
x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
}
int T,n,Q,a[N],dp[N][30],c[N],aa[N*10],bb[N];
struct node
{
int L,R,id;
} s[N];
int GC(int a,int b)
{
if(b==0) return a;
return GC(b,a%b);
}
void ED()
{
for(int i=0; i<n; i++) dp[i][0]=a[i];
for(int j=1; (1<<j)<=n; j++)
for(int i=0; i+(1<<j)-1<n; i++)
dp[i][j]=GC(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R)
{
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return GC(dp[L][k],dp[R-(1<<k)+1][k]);
}
bool cmp (node a,node b)
{
return a.R<b.R;
}
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int res=0;
for(int i=x; i>0; i=i-lowbit(i)) res=res+c[i];
return res;
}
void update(int x,int v)
{
for(int i=x; i<=n; i=i+lowbit(i)) c[i]=c[i]+v;
}
int main()
{
while(~scanf("%d%d",&n,&Q))
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
ED();
for(int i=0; i<Q; i++)
{
scanf("%d%d",&s[i].L,&s[i].R);
s[i].id=i;
}
sort(s,s+Q,cmp);
memset(aa,0,sizeof aa);
memset(c,0,sizeof c);
int p=0;
for(int i=0; i<n; i++)
{
int L=0,R=i,g=a[i];
while(1)
{
int l1=L,r1=R,l2,r2;
while(l1<=r1)
{
int mid=(l1+r1)/2;
if(RMQ(mid,i)==g)
l2=mid,r1=mid-1;
else l1=mid+1;
}
l1=L,r1=R,r2;
while(l1<=r1)
{
int mid=(l1+r1)/2;
if(RMQ(mid,i)==g)
r2=mid,l1=mid+1;
else
l1=mid+1;
}
l2++,r2++;
if(aa[g]>r2)
continue;
if(aa[g]!=0)
update(aa[g],-1);
update(r2,1);
aa[g]=r2;
l2--;
r2--;
R=l2-1;
if(R<0)
break;
g=RMQ(R,i);
}
while(p<Q&&s[p].R==i+1)
bb[s[p].id]=sum(s[p].R)-sum(s[p].L-1), p++;
}
for(int i=0; i<Q; i++)
printf("%d\n",bb[i]);
}
return 0;
}赛场超时代码：
————希望聚聚们看到能给优化一下
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=1e6+6;
int n,m,k,q,t,r,y,x;
int dp[N][20];
int aa[N],bb[N];
int cc[N],dd[N];
struct node
{
int u;
int v;
int m;
bool operator<(const node &tt)const
{
return v<tt.v;
}
} p[N];
struct node2
{
int u;
int v;
int m;
bool operator<(const node2 &tt)const
{
return m<tt.m;
}
} node2[N];
long long GC (int x,int y)
{
if(y==0)
return x;
return GC(y,x%y);
}
int SF(int u,int v)
{
int l=1,r=u;
while(l<r)
{
int e=(l+r)>>1;
int kk=u-e+1;
int xx=u,qq=-1;
for(int i=2; i>=0; --i)
{
if(kk&(1<<i))
{
if(qq==-1)
qq=dp[xx][i];
else
qq=GC(qq,dp[xx][i]);
xx-=(1<<i);
}
}
if(qq<v)
l=e+1;
else r=e;
}
return (l+r)>>1;
}
void add(int x,int t)
{
for(int i=x; i<=n; i+=i&(-i))
dd[i]+=t;
}
int get(int x)
{
int ans=0;
if(x==0)return 0;
for(int i=x; i>0; i-=i&(-i))
ans+=dd[i];
return ans;
}
void ED()
{
int xx=1;
for(int i=1; i<=m; ++i)
{
for(; xx<=y&&node2[xx].m<=p[i].v; ++xx)
{
int u=lower_bound(aa+1,aa+1+x,node2[xx].v)-aa;
if(node2[xx].u>bb[u])
{
if(bb[u])add(bb[u],-1);
add(node2[xx].u,1);
bb[u]=node2[xx].u;
}
}
cc[p[i].m]=get(p[i].v)-get(p[i].u-1);
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(aa,0,sizeof(aa));
memset(bb,0,sizeof(bb));
memset(cc,0,sizeof(cc));
memset(dd,0,sizeof(dd));
for(int i=1; i<=n; ++i)
scanf("%d",&dp[i][0]);
for(int i=1; i<=m; ++i)
{
scanf("%d%d",&p[i].u,&p[i].v);
p[i].m=i;
}
for(int k=1; (1<<k)<=n; ++k)
for(int i=n; i>1; --i)
{
int j=i-(1<<k)+1;
if(j<1)
break;
j=i-(1<<(k-1));
dp[i][k]=GC(dp[i][k-1],dp[j][k-1]);
}
x=0,y=0;
for(int i=1; i<=n; ++i)
{
q=-1;
for(int j=i; j>0; --j)
{
int ww=dp[j][0];
if(q!=-1)
ww=GC(ww,q);
q=ww;
y++;
node2[y].u=j,node2[y].m=i,node2[y].v=q;
aa[++x]=q;
j=SF(i,q);
}
}
sort(aa+1,aa+1+x);
x=unique(aa+1,aa+1+x)-aa-1;
sort(p+1,p+1+m);
sort(node2+1,node2+1+y);
ED();
for(int i=1; i<=m; ++i)
printf("%d\n",cc[i]);
}
return 0;
}