HDU 5869区间CGD不同种类数---树状数组+map统计区间不同种类数（离线）

131 阅读 0 评论 87 点赞

我是靠谱客的博主呆萌人生，这篇文章主要介绍HDU 5869区间CGD不同种类数---树状数组+map统计区间不同种类数（离线），现在分享给大家，希望可以做个参考。

http://acm.hdu.edu.cn/showproblem.php?pid=5869

题意：已知一个数组，Q个查询，问你区间子区间的不同GCD种类数

思路：先考虑一个数组区间不同个数，可以使用离线的树状数组实现，具体是对查询右端点进行排序，依次转移解决问题。

首先我们考虑固定右端点的查询区间不同数字，其实我们可以在每个数字出现的最右位置记录一下就可以了，统计起来就是sum[r]-sum[l]

这样子考虑右区间移动，就要改变那个数的最右位置，显然可以用一个map来维护每个数字出现的最右位置。

回到这个题目，显然一个点不只是一个数字，我们按照之前多校的一个处理方法，处理出来每个点作为右端点的子区间的GCD值（套路，而且一个点的不会很多，大致logAi个，用一个vector数组维护爽一下），这样子每个点就是一个数组了，但是统计的时候又不是区间所有点数组的不同数字个数，但是也很好魔改，其实我们只需要每个GCD出现的最右距离就可以了，因为如果查询的L在这个L左面，自然会被算进去，如果不在，那么就无视，以后的查询可能会需要，还是继续用map维护就好了。

所以这道题就解决啦！关键还是学会树状数组加map来统计区间不同种类数的方法。

代码：

复制代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
#define MAX 100005
const int INF=1e9+7;
int n,m;
int a[MAX];
int b[MAX];
int ans[MAX];
struct Q{
    int r,l,id;
}q[MAX];
vector<pair<int,int> > G[MAX];
map<int,int> H;

int lowbit(int x){
    return x & (-x);
}

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

int get_sum(int x){
    int ret=0;
    while(x!=0){
        ret+=b[x];
        x-=lowbit(x);
    }
    return ret;
}

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

bool cmp(const Q &q1,const Q &q2){
    if(q1.r!=q2.r)
    return q1.r<q2.r;
    else return q1.id<q2.id;
}

void F(int x){
    G[x].push_back(make_pair(a[x],x));
    int cnt=0;
    for(int i=0;i<G[x-1].size();i++){
        int gc=gcd(G[x-1][i].first,a[x]);
        if(gc!=G[x][cnt].first){
            G[x].push_back(make_pair(gc,G[x-1][i].second));
            cnt++;
        }
        else{
           // G[x][cnt].second=G[x-1][i].second;
        }
    }
}

void init(){
    for(int i=0;i<=n;i++) G[i].clear();
    H.clear();
    memset(b,0,sizeof(b));
    G[1].push_back(make_pair(a[1],1));
    for(int i=2;i<=n;i++) F(i);
}

int main(){
    int t;
    while (scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        init();
        int l,r;
        for(int i=0;i<m;i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q,q+m,cmp);
        int R=1;
        for(int i=0;i<m;i++){
            while(R<=q[i].r){
                for(int j=0;j<G[R].size();j++){
                    if(H.count(G[R][j].first)!=0){
                        modify(H[G[R][j].first],-1);
                    }
                    H[G[R][j].first]=G[R][j].second;
                    modify(G[R][j].second,1);
                }
                R++;
            }
            ans[q[i].id]=get_sum(q[i].r)-get_sum(q[i].l-1);
        }
        for(int i=0;i<m;i++) printf("%dn",ans[i]);

}
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
#define MAX 100005
const int INF=1e9+7;
int n,m;
int a[MAX];
int b[MAX];
int ans[MAX];
struct Q{
    int r,l,id;
}q[MAX];
vector<pair<int,int> > G[MAX];
map<int,int> H;

int lowbit(int x){
    return x & (-x);
}

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

int get_sum(int x){
    int ret=0;
    while(x!=0){
        ret+=b[x];
        x-=lowbit(x);
    }
    return ret;
}

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

bool cmp(const Q &q1,const Q &q2){
    if(q1.r!=q2.r)
    return q1.r<q2.r;
    else return q1.id<q2.id;
}

void F(int x){
    G[x].push_back(make_pair(a[x],x));
    int cnt=0;
    for(int i=0;i<G[x-1].size();i++){
        int gc=gcd(G[x-1][i].first,a[x]);
        if(gc!=G[x][cnt].first){
            G[x].push_back(make_pair(gc,G[x-1][i].second));
            cnt++;
        }
        else{
           // G[x][cnt].second=G[x-1][i].second;
        }
    }
}

void init(){
    for(int i=0;i<=n;i++) G[i].clear();
    H.clear();
    memset(b,0,sizeof(b));
    G[1].push_back(make_pair(a[1],1));
    for(int i=2;i<=n;i++) F(i);
}

int main(){
    int t;
    while (scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        init();
        int l,r;
        for(int i=0;i<m;i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q,q+m,cmp);
        int R=1;
        for(int i=0;i<m;i++){
            while(R<=q[i].r){
                for(int j=0;j<G[R].size();j++){
                    if(H.count(G[R][j].first)!=0){
                        modify(H[G[R][j].first],-1);
                    }
                    H[G[R][j].first]=G[R][j].second;
                    modify(G[R][j].second,1);
                }
                R++;
            }
            ans[q[i].id]=get_sum(q[i].r)-get_sum(q[i].l-1);
        }
        for(int i=0;i<m;i++) printf("%dn",ans[i]);

    }
    return 0;
}