hdu5869 Different GCD Subarray Query 线段树

75 阅读 0 评论 50 点赞

我是靠谱客的博主坦率机器猫，最近开发中收集的这篇文章主要介绍hdu5869 Different GCD Subarray Query 线段树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题解：考虑固定左端点的不同GCD值，只有不超过logA种, 所以事件点只有nlogA个. 那么离线处理, 按照区间右端点排序从小到大处理询问,

用一个树状数组维护每个GCD值的最大左端点位置即可. 复杂度是O(nlogAlogn).

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define getmid int mid=(l+r)>>1
#define maxn 110000
#define root 1,n,1
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define mp make_pair
struct node
{
    int id,l,r,ans;
}que[maxn];
int ans[maxn];
bool cmp1(node aa,node bb)
{
    if(aa.r!=bb.r) return aa.r<bb.r;
    return aa.l<bb.l;
}
bool cmp2(node aa,node bb)
{
    return aa.id<bb.id;
}
int gcd(int a,int b)
{
    if(a>b) swap(a,b);
    if(a==0) return b;
    return gcd(b%a,a);
}
int gd[maxn<<2],sum[maxn<<2],myp[maxn*10],seq[maxn],n;
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&gd[rt]);
        seq[l]=gd[rt];
        return;
    }
    getmid;
    build(lson);
    build(rson);
    gd[rt]=gcd(gd[rt<<1],gd[rt<<1|1]);
}
int query(int l,int r,int rt,int x,int y)
{
    if(x<=l&&r<=y) return gd[rt];
    getmid;
    int g1=0,g2=0;
    if(x<=mid) g1=query(lson,x,y);
    if(y>mid) g2=query(rson,x,y);
    return gcd(g1,g2);
}
int qsum(int l,int r,int rt,int x,int y)
{
    if(x<=l&&r<=y) return sum[rt];
    getmid;
    int s1=0,s2=0;
    if(x<=mid) s1=qsum(lson,x,y);
    if(y>mid) s2=qsum(rson,x,y);
    return s1+s2;
}
void update(int l,int r,int rt,int pos,int f)
{
    if(l==r)
    {
        sum[rt]+=f;
        return;
    }
    getmid;
    if(pos<=mid) update(lson,pos,f);
    else update(rson,pos,f);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
pii queryl (int l,int r,int rt,int R,int v)
{
    if (r<=R)
    {
        if (gd[rt]%v==0) return pii(v,l) ;
        else if (l==r) return pii ( gcd(v,gd[rt]), l) ;
    }
    getmid;
    if ( R <= mid ) return queryl (lson,R,v) ;
    pii tmp = queryl(rson,R,v) ;
    if ( tmp.ft < v ) return tmp;
    return queryl (lson,R,v) ;
}
vector<pii>seggd;
vector<node>q[maxn];
void getl(int i)
{
    seggd.clear();
    int nowgcd=seq[i],lastgcd = query( 1,n,1 ,1,i),x=i;
    seggd.pb(pii(seq[i],i));
    while ( nowgcd != lastgcd )
    {
        pii y=queryl(1,n,1,x,nowgcd) ;
        seggd.pb(y);
        x=y.sd;
        nowgcd=y.ft;
    }
}
void cn()
{
    memset(myp,0,sizeof(myp));
    memset(gd,0,sizeof(gd));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++) q[i].clear();
}
int main()
{
    int m;
    while(~scanf("%d%d",&n,&m))
    {
        build(1,n,1);
        int l,r;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&que[i].l,&que[i].r);
            que[i].id=i;
            q[que[i].r].pb((que[i]));
        }
        for(int i=1;i<=n;i++)
        {
            getl(i);
            for(int j=0;j<seggd.size();j++)
            {
                if(myp[seggd[j].ft])
                {
                   update(1,n,1,myp[seggd[j].ft],-1);
                }
                myp[seggd[j].ft]=seggd[j].sd;
                update(1,n,1,seggd[j].sd,1);
            }
            for(int j=0;j<q[i].size();j++)
            {
                ans[q[i][j].id]=qsum(1,n,1,q[i][j].l,i);
            }
        }
        for(int i=1;i<=m;i++) printf("%dn",ans[i]);
        cn();
    }
    return 0;
}
/*
5 3
1 3 4 4 4
3 5
2 5
1 5
*/