CF #271 F Ant colony 树

来源： 本站

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string>
 5 #include <string.h>
 6 #include <stdio.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #include <ctime>
14 #include <numeric>
15 #include <cassert>
16 
17 using namespace std;
18 
19 const int N=1e5+10;
20 
21 int s[N];
22 pair<int,int> d[N];
23 int t[N<<2];
24 
25 int gcd(int a,int b){
26     if (b==0) return a;
27     return gcd(b,a%b);
28 }
29 void up(int rt) {
30     t[rt]=gcd(t[rt<<1],t[rt<<1|1]);
31 }
32 void build(int l,int r,int rt) {
33     if (l==r){
34         t[rt]=s[l];
35         return;
36     }
37     int m=(l+r)>>1;
38     build(l,m,rt<<1);
39     build(m+1,r,rt<<1|1);
40     up(rt);
41 }
42 int ask(int L,int R,int l,int r,int rt) {
43     if (L<=l&&r<=R) {
44         return t[rt];
45     }
46     int m=(l+r)>>1;
47     int ret=0,u=0,v=0;
48     if (L<=m)
49         u=ask(L,R,l,m,rt<<1);
50     if (R>m)
51         v=ask(L,R,m+1,r,rt<<1|1);
52     return gcd(u,v);
53 }
54 int main () {
55     int n;
56     scanf("%d",&n);
57     for (int i=1;i<=n;i++) {
58         scanf("%d",s+i);
59         d[i-1]=make_pair(s[i],i);
60     }
61     build(1,n,1);
62     sort(d,d+n);
63     int m;
64     scanf("%d",&m);
65     while (m--) {
66         int l,r;
67         scanf("%d %d",&l,&r);
68         int g=ask(l,r,1,n,1);
69         int u=lower_bound(d,d+n,make_pair(g,l))-d;
70         int v=lower_bound(d,d+n,make_pair(g,r+1))-d;
71         printf("%d
",r-l+1-(v-u));
72         //printf("%d %d %d
",g,u,v);
73     }
74     return 0;
75 }