HDU 5869 Different GCD Subarray Query 离线+树状数组

时间：2022-11-07 17:16:23

Different GCD Subarray Query

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
 

题意：

　　长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.

题解：

　　固定右端点

　　预处理出 每个点向左延伸 的 不同gcd值

　　这样的 值不会超过log a 个

　　然后问题就变成了 问你一段区间内不同 gcd 值有多少，值是很少的 （询问一个区间有多少颜色的题型）

　　树状数组维护就可以了

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 1e6+, M = 1e2+, mod = 1e9+, inf = 2e9;

int n,q,a[N],ans[N];

int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b);}

vector<pii> G[N];

struct QQ{

        int l,r,id;

        bool operator < (const QQ &a) const {

             return a.r > r;

        }

}Q[N];

int C[N],vis[N];

void update(int x,int c) {

        for(int i =x; i < N; i+=i&(-i)) C[i] += c;

}

int ask(int x) {

        int s = ;

        for(int i = x; i; i-= i & (-i))s += C[i];

        return s;

}

int main() {

        while(scanf("%d%d",&n,&q)!=EOF) {

            for(int i = ; i <= n; ++i) scanf("%d",&a[i]);

            for(int i = ; i <= n; ++i) G[i].clear();

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

                    int x = a[i];

                    int y = i;

                    for(int j = ; j < G[i-].size(); ++j) {

                        int res = gcd(x,G[i-][j].first);

                        if(x != res) {

                                G[i].push_back(MP(x,y));

                                x = res;

                                y = G[i-][j].second;

                        }

                    }

                    G[i].push_back(MP(x,y));

            }

            memset(C,,sizeof(C));

            memset(vis,,sizeof(vis));

            for(int i = ; i <= q; ++i) {scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id = i;}

            sort(Q+,Q+q+);

            for(int R = , i = ; i <= q; ++i) {

                    while(R < Q[i].r) {

                        R++;

                        for(int j = ; j < G[R].size(); ++j) {

                            int res = G[R][j].first;

                            int ids = G[R][j].second;

                            if(vis[res]) update(vis[res],-);

                            vis[res] = ids;

                            update(vis[res],);

                        }

                    }

                    ans[Q[i].id] = ask(R) - ask(Q[i].l-);

            }

            for(int i = ; i <= q; ++i) cout<<ans[i]<<endl;

        }

        return ;

}

相关文章