hdu5726 && hdu5869

hdu5726 GCD

题意：n个数，q次询问，每次询问给出(l,r)，问区间的gcd，并且有多少个区间和这个区间gcd相同

题解：求区间啊gcd比较简单，直接线段树就可以，怎么求有多少个区间呢？

            假设知道了处理到上一位的gcd都有哪些，那么通过上一位的gcd，就可以求出到本位的所有的gcd

            性质，n个数，所有数可能组成的gcd，有大概log(n)个

struct node {
    int l, r;
    LL gcd;
}tree[N*4];

LL a[N];

void push(int rt){
    tree[rt].gcd = __gcd(tree[rt*2].gcd,tree[rt*2+1].gcd);
}

void build(int l, int r, int rt){
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r){
        tree[rt].gcd = a[l];
        return ;
    }
    int mid = (l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    push(rt);
}

LL query(int l, int r, int rt){
    if(l<=tree[rt].l && tree[rt].r<=r){
        return tree[rt].gcd;
    }
    int mid = (tree[rt].l+tree[rt].r)/2;
    LL ans = 0;
    if(l<=mid) ans = __gcd(ans,query(l,r,rt*2));
    if(mid+1<=r) ans = __gcd(ans,query(l,r,rt*2+1));
    return ans;
}

int n;
map <LL, LL> ans;
map <LL, LL> ans1;
map <LL, LL> ans2;

int main(){
    int t;
    cin>>t;
    for(int ii=1;ii<=t;ii++){
        cin>>n;
        ans.clear();
        ans1.clear();
        ans2.clear();
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
        }
        build(1,n,1);
        ans1[a[1]]++;
        ans[a[1]]++;
        for(int i=2;i<=n;i++){
            LL temp = a[i];
            ans2[temp]++;
            ans[temp]++;
            for(map<LL, LL>::iterator it = ans1.begin();it!=ans1.end();it++){
                int tt = __gcd(it->first,temp);
                ans[tt] += it->second;
                ans2[tt] += it->second;
                //cout<<ans[1]<<endl;
            }
            ans1.clear();
            for(map<LL, LL>::iterator it = ans2.begin();it!=ans2.end();it++){
                ans1[it->first] = it->second;
            }
            ans2.clear();
        }
        //cout<<ans[1];
        int q,l,r;
        cin>>q;
        printf("Case #%d:n",ii);
        while(q--){
            scanf("%d%d",&l,&r);
            LL temp = query(l,r,1);
            printf("%I64d %I64dn",temp,ans[temp]);
        }
    }
    return 0;
}

题意：n个数，q次询问，每次询问给出(l,r)，问区间中连续子区间可能的gcd共有多少种

题解：是上面那个的加强版，离线，从左往右处理，处理到这一位时，处理出所有可能的gcd，考虑一个可能已经出现过的gcd，标记这个gcd出现的最右端，越往右肯定越优，然后再把出现的位置放在树状数组中，每次只要查询那个区间就可以

struct node {
    int l, r;
    LL gcd;
}tree[N*4];

struct po{
    int l,r,id,ans;
}p[100010];

bool cmp1(po a,po b){
    if(a.r == b.r) return a.l<b.l;
    else return a.r<b.r;
}

bool cmp2(po a,po b){
    return a.id<b.id;
}

int a[N];

int b[N],n;

int sum(int x){
    int ans=0;
    while(x>0){
        ans+=b[x];
        x-=lowbit(x);
    }
    return ans;
}

void add(int x,int sum){
    while(x<=n){
        b[x]+=sum;
        x+=lowbit(x);
    }
}

void push(int rt){
    tree[rt].gcd = __gcd(tree[rt*2].gcd,tree[rt*2+1].gcd);
}

void build(int l, int r, int rt){
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r){
        tree[rt].gcd = a[l];
        return ;
    }
    int mid = (l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    push(rt);
}

LL query(int l, int r, int rt){
    if(l<=tree[rt].l && tree[rt].r<=r){
        return tree[rt].gcd;
    }
    int mid = (tree[rt].l+tree[rt].r)/2;
    LL ans = 0;
    if(l<=mid) ans = __gcd(ans,query(l,r,rt*2));
    if(mid+1<=r) ans = __gcd(ans,query(l,r,rt*2+1));
    return ans;
}

map <LL, LL> ans;
map <LL, LL> ans1;
map <LL, LL> ans2;

int weizhi[1000010];

int main(){
    int q;
    while(cin>>n>>q){
        ans.clear();
        ans1.clear();
        ans2.clear();
        memset(b,0,sizeof(b));
        memset(weizhi,0,sizeof(weizhi));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<q;i++){
            scanf("%d%d",&p[i].l,&p[i].r);
            p[i].id=i;
        }
        sort(p,p+q,cmp1);
        build(1,n,1);
        ans1[a[1]]++;
        ans[a[1]]++;
        ///开头第一个数
        add(1,1);
        int num=0;
        weizhi[a[1]]=1;
        while(p[num].r==1){
            p[num].ans=1;
            num++;
        }
        for(int i=2;i<=n;i++){
            LL temp = (LL)a[i];
            ans2[temp]++;
            ans[temp]++;
            ///要先处理这个遇到的数
            if(weizhi[a[i]]==0){
                add(i,1);
            }
            else {
                add(weizhi[a[i]],-1);
                add(i,1);
            }
            ///当前gcd的值，出现在这个位置肯定是最优的
            weizhi[temp]=i;
            for(map<LL, LL>::iterator it = ans1.begin();it!=ans1.end();it++){
                int tt = __gcd(it->first,temp);
                ans[tt] += it->second;
                ans2[tt] += it->second;
                ///如果没有出现过这个gcd
                if(weizhi[tt]==0){
                    weizhi[tt]=weizhi[it->first];
                    add(weizhi[tt],1);
                }
                ///如果出现过这个gcd
                else {
                    int temp=weizhi[tt];
                    ///这个需要比较，贡献1wa
                    if(temp < weizhi[it->first]){
                        add(temp,-1);
                        add(weizhi[it->first],1);
                        weizhi[tt]=weizhi[it->first];
                    }
                }
            }
            ans1.clear();
            for(map<LL, LL>::iterator it = ans2.begin();it!=ans2.end();it++){
                ans1[it->first] = it->second;
            }
            ans2.clear();
            while(p[num].r==i){
                p[num].ans=sum(p[num].r)-sum(p[num].l-1);
                num++;
            }
        }
        sort(p,p+q,cmp2);
        for(int i=0;i<q;i++){
            printf("%dn",p[i].ans);
        }
    }
    return 0;
}

最后

以上就是怕黑小熊猫为你收集整理的hdu5726 && hdu5869的全部内容，希望文章能够帮你解决hdu5726 && hdu5869所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。