HDU-5869 Different GCD Subarray Query(树状数组)

先不考虑查询的区间$[L,R]$

首先我们枚举一个$\gcd$区间的$l$，考虑不同的$\gcd(l..r)$实际上只有$\log n$个，因为每次改变，$\gcd$的值至少减少一倍

维护一个倍增数组，可以$\log n$二分出下一个$\gcd$不同的$r$，统计出每一个的$r$，那么就能得到$n\log n$个不同的区间

问题就转化为求$[L,R]$包含的权值不同的$[l,r]$个数

那么可以把同一种权值的区间拉出来，离线之后，按照$l$和$L$倒序，每次对于$[l,r]$更新的区间就是$r$到这个权值之前出现过的最小$r$

一共有$n\log n$个更新，用树状数组维护区间更新，复杂度$O(n\log^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
const int N=1e5+10,P=1e9+7;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }

int n,m;
int a[N];

struct BIT{
	int s[N];
	void clear(){ rep(i,1,n) s[i]=0; }
	void Add(int p,int x) { while(p<=n) s[p]+=x,p+=p&-p; }
	int Que(int p){ 
		int res=0; 
		while(p) res+=s[p],p-=p&-p; 
		return res;
	}
}Tree;

struct Query{ int p,id; };
struct Update{ int p,x; };
vector <Query> Q[N];
vector <Update> U[N];
int A[N],ans[N],G[N][18];


int apr[N],apc,mk[N*10];
void AddUpdate(int l,int r,int x) {
	if(!mk[x]) apr[++apc]=x,mk[x]=n+1;
	if(r>=mk[x]) return;
	U[l].pb((Update){r,1}),U[l].pb((Update){mk[x],-1});
	mk[x]=r;
}

int main(){
	while(~scanf("%d%d",&n,&m)) {
		rep(i,1,n) {
			A[i]=rd(),Q[i].clear(),U[i].clear();
		}
		drep(i,n,1) {
			G[i][0]=A[i];
			for(int j=1;i+(1<<j)<=n+1;++j) G[i][j]=gcd(G[i][j-1],G[i+(1<<(j-1))][j-1]);
			int x=A[i],r=i;
			while(r<=n) {
				AddUpdate(i,r,x);
				drep(j,17,0) if(r+(1<<j)<=n+1 && G[r][j]%x==0) r+=1<<j;
				x=gcd(x,A[r]);
			}
		}
		rep(i,1,m) {
			int l=rd(),r=rd();
			Q[l].pb((Query){r,i});
		}
		Tree.clear();
		drep(i,n,1) {
			for(auto j:U[i]) Tree.Add(j.p,j.x);
			for(auto j:Q[i]) ans[j.id]=Tree.Que(j.p);
		}
		rep(i,1,m) printf("%d\n",ans[i]);
		rep(i,1,apc) mk[apr[i]]=0; apc=0;
	}
}