HDU 5869 Different GCD Subarray Query （树状数组）

拼搏现实的明天。 2022-07-16 04:21 21阅读 0赞

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

题目大意：找出一个区间内子区间一共有多少种不同的GCD

解题思路：  
预处理出0到r区间内共有多少种不同的GCD(0<=r&&r小于n\]，并求出每种不同的GCD最靠右的位置，如何预处理出上述区间的值呢，我们假设找到了\[0,r-1)区间的所有GCD值，\[0,r)区间的所有GCD值就是a\[r-1\]和之前区间的所有GCD值一一求GCD并记录此种GCD值最靠右的位置。  
然后我们将答案按右端点从小到大排序，假设右端点为r1,我们找出\[0,r)  
(0<=r<=r1)所有区间出现过的所有GCD值，并建立树状数组，在每种GCD值出现的最右端位置加1，因为左端点只要能到小于等于其某个GCD最右端的值，这个区间里便能包括此GCD，然后求一下区间和即可。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    int n,q;
    
    struct VAL
    {
        int val;
        int poi;
    } ;
    
    struct P
    {
        int l,r,poi,ans;
    };
    
    int have[1000005];
    
    bool cmp1(P p1,P p2)
    {
        return p1.r<p2.r;
    }
    
    bool cmp2(P p1,P p2)
    {
        return p1.poi<p2.poi;
    }
    
    int a[100005];
    P p[100005];
    int tree[100005];
    
    vector<VAL> vec[100005];
    
    int lowbit(int x)
    {
        return x&(-x);
    }
    
    void modify(int x,int add)
    {
        while(x<=n)
        {
            tree[x]+=add;
            x+=lowbit(x);
        }
    }
    
    int getsum(int x)
    {
        int ret=0;
        while(x!=0)
        {
            ret+=tree[x];
            x-=lowbit(x);
        }
        return ret;
    }
    
    int main()
    {
        while(RII(n,q)!=EOF)
        {
            for(int i=1; i<=n; i++)
                RI(a[i]);
            for(int i=1; i<=q; i++)
            {
                RII(p[i].l,p[i].r);
                p[i].poi=i;
            }
    
    
            memset(have,0,sizeof(have));
    
            for(int i=1; i<=n; i++)
            {
                VAL v;
                v.poi=i;
                v.val=a[i];
                vec[i].push_back(v);
                have[a[i]]=1;
    
                for(int j=0; j<vec[i-1].size(); j++)
                {
                    int ex=__gcd(vec[i-1][j].val,a[i]);
                    if(!have[ex])
                    {
                        VAL v;
                        v.poi=vec[i-1][j].poi;
                        v.val=ex;
                        vec[i].push_back(v);
                        have[ex]=1;
                    }
                }
                for(int j=0;j<vec[i].size();j++)
                {
                    have[vec[i][j].val]=0;
                }
    
            }
            sort(p+1,p+q+1,cmp1);
            int now=0;
            memset(tree,0,sizeof(tree));
            for(int i=1;i<=q;i++)
            {
                while(now<p[i].r)
                {
                    now++;
                    for(int j=0;j<vec[now].size();j++)
                    {
                        int x=have[vec[now][j].val];
                        if(x)
                        {
                            modify(x,-1);
                        }
                        modify(vec[now][j].poi,1);
                        have[vec[now][j].val]=vec[now][j].poi;
                    }
                }
                p[i].ans=getsum(p[i].r)-getsum(p[i].l-1);
            }
            sort(p+1,p+q+1,cmp2);
    
            for(int i=1;i<=q;i++)
            {
                printf("%d\n",p[i].ans);
            }
            for(int i=0;i<=n;i++)
                vec[i].clear();
    
        }
    
    
        return 0;
    }