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

2017-01-29 23:14:26 Tabris_ 阅读数：240

博客爬取于2020-06-14 22:41:55
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54780836

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5869

---------------------------------------------------------------------------------------------------------.
Different GCD Subarray Query

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1172 Accepted Submission(s): 444

Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:

Given an array a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].

Input
There are several tests, process till the end of input.

For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.

You can assume that

1≤N,Q≤100000

1≤ai≤1000000

Output
For each query, output the answer in one line.

Sample Input
5 3
1 3 4 6 9
3 5
2 5
1 5

Sample Output
6
6
6

Source
2016 ACM/ICPC Asia Regional Dalian Online

---------------------------------------------------------------------------------------------------------.
题目大意:
给长度为N的序列,M次询问，每次询问【L,R】之间所有子区间的不同GCD有多少个、

解题思路:
固定左端点，然后离线预处理出结果，用树状数组或者线段树均可。

首先预处理出每一个查询右区间位置渐近到达1位置的所有gcd的结果,这个结果显然是单调递减的,且不超过
O(log2ar)O(log_{2}{a_r})个数的, 这个显然很好想…

然后在采取更新数值,
将每一个新旧的gcd更新到树状数组即使的最靠右的位置(+1,-1),即可,每一次查询的时候 就直接在树状数组查询区间里的个数就行了.

然后vis[1e6]居然RE。。。。最后改了map才过、

时间复杂度O(N∗log2A∗log2n)O(N*log_{2}{A}*log_{2}{n})

附本题代码
---------------------------------------------------------------------------------------------------------.

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

# 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;
}