hdu 5869 Different GCD Subarray Query

122 阅读 0 评论 81 点赞

我是靠谱客的博主合适花卷，这篇文章主要介绍hdu 5869 Different GCD Subarray Query，现在分享给大家，希望可以做个参考。

题目链接如下：

Problem - 5869

这里用每个区间我们利用GCD的传递性。记录每个GCD的最左区间。

我们按照右区间，左区间的优先次序对区间进行排序。

这里的update用于当左区间更新的时候，而左区间更新的时候其实是在新的数字加进来之后发生的，如果我们在相同的一个因子，这个因子有更右的左区间，那么我们的update用处是把之前的那一份减掉1，把新的区间点加进来，这么做，我的理解就是去重。。。而且在后续的处理过程中右区间是超过当前位置的，所以应该要保证左区间尽可能接近右区间这样？因为如果在更左边的区间的话有可能是会统计错误的。

代码如下所示：

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<climits>

using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
const int MAXN=100001;
int tree[MAXN<<2];
struct q{
    int l,r,id;
    bool operator<(const struct q &rhs) const{
        if (r!=rhs.r){
            return r<rhs.r;
        }
        return l<rhs.l;
    }
}ask[MAXN];
int ans[MAXN];
int has[MAXN*10];
vector<pair<int,int>> vec[MAXN];// 装载第i个输入的数的最大公约数以及其最左区间
void build(int l,int r,int rt){
    tree[rt]=0;
    if (l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
}

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

void update(int pos,int val,int l,int r,int rt){
    tree[rt]+=val;
    if (l==r){
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid){
        update(pos,val,lson);
    } else{
        update(pos,val,rson);
    }
}

int query(int a,int b,int l,int r,int rt){
    if (a<=l && r<=b) return tree[rt];
    int mid=(l+r)>>1;
    int res=0;
    if (a<=mid){
        res+= query(a,b,lson);
    }
    if (b>mid){
        res+= query(a,b,rson);
    }
    return res;
}

int main(){
    int n,m;
    while (~scanf("%d %d",&n,&m)){
        for (int i = 0; i <= n; ++i) {
            vec[i].clear();
        }
        for (int i = 1; i <= n; ++i) {
            int x;
            scanf("%d",&x);
            int y=i;
            int t;
            for (int j = 0; j < vec[i-1].size(); ++j) {
                t= gcd(vec[i-1][j].first,x);
                if (t!=x){
                    vec[i].push_back({x,y});
                    x=t,y=vec[i-1][j].second;
                }
            }
            vec[i].push_back({x,y});
        }
        build(1,n,1);
        for (int i = 1; i <= m; ++i) {
            scanf("%d %d",&ask[i].l,&ask[i].r);
            ask[i].id=i;
        }
        sort(ask+1,ask+1+m);
        int cur=1;
        memset(has,0,sizeof(has));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < vec[i].size(); ++j) {
                int u=vec[i][j].first, v=vec[i][j].second;
                if (has[u]<v){
                    if (has[u]){
                        update(has[u],-1,1,n,1);
                    }
                    update(v,1,1,n,1);
                    has[u]=v;
                }
            }
            for (int j = cur; j <= m && ask[j].r<=i; ++j) {
                ans[ask[j].id]= query(ask[j].l,ask[j].r,1,n,1);
                cur=j+1;
            }
        }
        for (int i = 1; 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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<climits>

using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
const int MAXN=100001;
int tree[MAXN<<2];
struct q{
    int l,r,id;
    bool operator<(const struct q &rhs) const{
        if (r!=rhs.r){
            return r<rhs.r;
        }
        return l<rhs.l;
    }
}ask[MAXN];
int ans[MAXN];
int has[MAXN*10];
vector<pair<int,int>> vec[MAXN];// 装载第i个输入的数的最大公约数以及其最左区间
void build(int l,int r,int rt){
    tree[rt]=0;
    if (l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
}

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

void update(int pos,int val,int l,int r,int rt){
    tree[rt]+=val;
    if (l==r){
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid){
        update(pos,val,lson);
    } else{
        update(pos,val,rson);
    }
}

int query(int a,int b,int l,int r,int rt){
    if (a<=l && r<=b) return tree[rt];
    int mid=(l+r)>>1;
    int res=0;
    if (a<=mid){
        res+= query(a,b,lson);
    }
    if (b>mid){
        res+= query(a,b,rson);
    }
    return res;
}

int main(){
    int n,m;
    while (~scanf("%d %d",&n,&m)){
        for (int i = 0; i <= n; ++i) {
            vec[i].clear();
        }
        for (int i = 1; i <= n; ++i) {
            int x;
            scanf("%d",&x);
            int y=i;
            int t;
            for (int j = 0; j < vec[i-1].size(); ++j) {
                t= gcd(vec[i-1][j].first,x);
                if (t!=x){
                    vec[i].push_back({x,y});
                    x=t,y=vec[i-1][j].second;
                }
            }
            vec[i].push_back({x,y});
        }
        build(1,n,1);
        for (int i = 1; i <= m; ++i) {
            scanf("%d %d",&ask[i].l,&ask[i].r);
            ask[i].id=i;
        }
        sort(ask+1,ask+1+m);
        int cur=1;
        memset(has,0,sizeof(has));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < vec[i].size(); ++j) {
                int u=vec[i][j].first, v=vec[i][j].second;
                if (has[u]<v){
                    if (has[u]){
                        update(has[u],-1,1,n,1);
                    }
                    update(v,1,1,n,1);
                    has[u]=v;
                }
            }
            for (int j = cur; j <= m && ask[j].r<=i; ++j) {
                ans[ask[j].id]= query(ask[j].l,ask[j].r,1,n,1);
                cur=j+1;
            }
        }
        for (int i = 1; i <= m; ++i) {
            printf("%dn",ans[i]);
        }
    }
    return 0;
}