HDU - 5869 Different GCD Subarray Query（树状数组或线段树+rmq）

75 阅读 0 评论 50 点赞

我是靠谱客的博主自由玉米，最近开发中收集的这篇文章主要介绍HDU - 5869 Different GCD Subarray Query（树状数组或线段树+rmq），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：给你一组数, 然后是m个查询. 问[l,r]中所有连续区间共有多少不同的GCD

思路：每个数往两边扩找不同的gcd，最多能找log个，gcd就会变成1。一开始想的是rmq处理出以每个数为起点往左往右扩展开的首次出现与上一次不同的gcd位置，然后离线用莫队来搞，时间复杂度很高，当时没有想到别的思路，然后敲完后一直re.....

事实上这个题应该是线段树或者树状数组，很套路的一个做法。把查询根据右端点排序。然后不断更新最后能产生gcd的最左边的位置，pos往后走，查询答案。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define pb push_back
const int maxn=2e5+10;
int a[maxn],n,m;
int g[maxn][22],mm[maxn];
void initRMQ()
{
    mm[0]=-1;
    for(int i=1;i<=n;i++)
    {
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        g[i][0]=a[i];
    }
    for(int j=1;j<=mm[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            g[i][j]=__gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
    }
}
int rmq_gcd(int l,int r)
{
    int k=mm[r-l+1];
    return __gcd(g[l][k],g[r-(1<<k)+1][k]);
}
struct node{
    int l,r,id;
}s[maxn];
bool cmp(const node &x,const node &y)
{
    if(x.r==y.r)
    return x.l<y.l;
    return x.r<y.r;
}
const int N=1e6;
int c[N+10],book[N+10];
void update(int pos,int val)
{
    for(int i=pos;i<=N;i+=i&-i)
        c[i]+=val;
}
int query(int pos)
{
    int ans=0;
    for(int i=pos;i>0;i-=i&-i)
        ans+=c[i];
    return ans;
}
int ans[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        initRMQ();

        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&s[i].l,&s[i].r);
            s[i].id=i;
        }
        sort(s+1,s+m+1,cmp);

        for(int i=1;i<=N;i++)
            c[i]=book[i]=0;
        int pos=1;
        for(int i=1;i<=n;i++)
        {
            int gc=0,kt=i;
            while(gc!=1&&kt>=1)
            {
                int mid,k,l=1,r=kt;
                while(l<=r)
                {
                    mid=(l+r)>>1;
                    if(rmq_gcd(mid,i)!=gc)
                    {
                        k=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                gc=rmq_gcd(k,i);
                if(!book[gc])
                {
                    update(k,1);
                    book[gc]=k;
                }
                else
                if(book[gc]<k)
                {
                    update(book[gc],-1);
                    update(k,1);
                    book[gc]=k;
                }
                kt=k-1;
            }
            while(pos<=m&&s[pos].r==i)
            {
                ans[s[pos].id]=query(s[pos].r)-query(s[pos].l-1);
                pos++;
            }
        }
        for(int i=1;i<=m;i++)
            printf("%dn",ans[i]);
    }
    return 0;
}