rmq +二分暴力 hdu 5726

参考博客

题意：n 个数字的数列，有m个询问：求出  L   到   R 的  gcd（最大公约数 ），然后问这整个序列中有多少个区间的  gcd  和这个一样。

分析：L 到  R的gcd直接用RMQ的ST算法求，第二步，我们可以枚举左端点 i 从1-n，对每个i，二分右端点，计算每种gcd值的数量，因为如果左端点固定，gcd值随着右端点的往右，呈现单调不增，而且gcd值每次变化，至少除以2，所以gcd的数量为nlog2(n)种，可以开map<int,long long>存每种gcd值的数量。

代码：

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

typedef long long ll;

using namespace std;

const int max_=1e5+;

int dp[max_][];//st表

int a[max_];

map<int,ll>mp;//gcd的个数。

int gcd(int x,int y)

{

    if(y==)

        return x;

    else

        return gcd(y,x%y);

}

void RMQ_ST(int n)

{

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

        dp[i][]=a[i];

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)

    {

        dp[i][j]=gcd(dp[i][j-],dp[i+(<<(j-))][j-]);

    }

}

int RMQ_question(int L,int R)

{

    int k=;

    while((<<(k+))<=R-L+)k++;

    return gcd(dp[L][k],dp[R+-(<<k)][k]);

}

void search_gcd(int n)

{

        mp.clear();

    for(int i=;i<=n;i++)//枚举左端点

    {

        int g=a[i];

        int j=i;

        while(j<=n)//二分搜索

        {

            int l=j;

            int r=n;

            while(l<r)

            {

                int mid=(l+r+)/;

                if(RMQ_question(i,mid)==g)

                    l=mid;

                else

                    r=mid-;

            }

            mp[g]+=l-j+;

            j=l+;

            g=RMQ_question(i,j);

        }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int testcase=;testcase<=T;testcase++)

    {

        int n;

       scanf("%d",&n);

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

        {

           scanf("%d",&a[i]);

        }

        RMQ_ST(n);

        search_gcd(n);

        int m;

       scanf("%d",&m);

        printf("Case #%d:\n",testcase);

        for(int i=;i<m;i++)

        {

           int l,r;

           scanf("%d %d",&l,&r);

           int g=RMQ_question(l,r);

           ll  sum=mp[g];

          printf("%d %lld\n",g,sum);

        }

    }

}