hdu5726 && hdu5869

110 阅读 0 评论 73 点赞

我是靠谱客的博主怕黑小熊猫，这篇文章主要介绍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;
}

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
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;
}

hdu5869 Different GCD Subarray Query

题意：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);
}

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;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
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;
}