HDU - 5869 Different GCD Subarray Query GCD+离线+树状数组（区间不同gcd的个数）

142 阅读 0 评论 94 点赞

我是靠谱客的博主典雅草莓，这篇文章主要介绍HDU - 5869 Different GCD Subarray Query GCD+离线+树状数组（区间不同gcd的个数），现在分享给大家，希望可以做个参考。

题目链接

题意：

给定一个a数组，每次询问一个区间[l,r]求这个区间内所有子区间的gcd的种类。

思路：

这个题目类似于区间不同数的个数

首先知道gcd的性质,在固定一个端点的情况下,连续区间的gcd的个数最多为log级别的.
我们可以固定每个点作为右端点,然后预处理出以该点为右端点的所有不同gcd的情况,相同gcd的取左端点大的.最后离线处理所有的询问,用树状数组维护一下即可》

复制代码

#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
using namespace std;

const int maxn = 1e6+5;
typedef long long ll;
int n,q;
vector<pair<int,int> > vt[maxn];
int s[maxn],vis[maxn],ans[maxn],a[maxn];
struct node
{
    int l,r,id;
    bool operator <(const node & w) const
    {
        return r < w.r;
    }
}op[maxn];
int lowbit(int x){
    return x & -x;
}
void add(int x,int d)
{
    while(x < maxn)
    {
        s[x] += d;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int res = 0;
    while(x)
    {
        res += s[x];
        x -= lowbit(x);
    }
    return res;
}
void init()
{
    memset(s,0,sizeof s);
    memset(vis,0,sizeof vis);
    for(int i = 0;i < maxn;++i)
    vt[i].clear();
}
void solve()
{
    for(int i = 1;i <= n;++i)
    {
        vt[i].pb(mk(a[i],i));
        int pre = a[i];
        for(int j = 0;j < vt[i-1].size();++j)
        {
            int tmp = __gcd(vt[i-1][j].first,a[i]);
            if(tmp != pre)
            vt[i].pb(mk(tmp,vt[i-1][j].second)),pre = tmp;
        }
    }
    int cur = 0;
    for(int i = 1;i <= q;++i)
    {
        while(cur < op[i].r)
        {
            cur++;
            for(int j = 0;j < vt[cur].size();++j)
            {
                int tmp = vt[cur][j].first;
                int pos = vt[cur][j].second;
                if(vis[tmp]) add(vis[tmp],-1);
                vis[tmp]=pos;
                add(pos,1);
            }
        }
        ans[op[i].id] = sum(op[i].r)-sum(op[i].l-1);
    }
    for(int i = 1;i <= q;++i)
    printf("%dn",ans[i]);
}
int main()
{

while(~scanf("%d %d",&n,&q))
    {
        init(); 
        for(int i = 1;i <= n;++i)
        scanf("%d",&a[i]);
        for(int i = 1;i <= q;++i)
        {
            scanf("%d %d",&op[i].l,&op[i].r);
            op[i].id = i;
        }
        sort(op+1,op+1+q);
        solve();
    }
    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
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
using namespace std;

const int maxn = 1e6+5;
typedef long long ll;
int n,q;
vector<pair<int,int> > vt[maxn];
int s[maxn],vis[maxn],ans[maxn],a[maxn];
struct node
{
    int l,r,id;
    bool operator <(const node & w) const
    {
        return r < w.r;
    }
}op[maxn];
int lowbit(int x){
    return x & -x;
}
void add(int x,int d)
{
    while(x < maxn)
    {
        s[x] += d;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int res = 0;
    while(x)
    {
        res += s[x];
        x -= lowbit(x);
    }
    return res;
}
void init()
{
    memset(s,0,sizeof s);
    memset(vis,0,sizeof vis);
    for(int i = 0;i < maxn;++i)
    vt[i].clear();
}
void solve()
{
    for(int i = 1;i <= n;++i)
    {
        vt[i].pb(mk(a[i],i));
        int pre = a[i];
        for(int j = 0;j < vt[i-1].size();++j)
        {
            int tmp = __gcd(vt[i-1][j].first,a[i]);
            if(tmp != pre)
            vt[i].pb(mk(tmp,vt[i-1][j].second)),pre = tmp;
        }
    }
    int cur = 0;
    for(int i = 1;i <= q;++i)
    {
        while(cur < op[i].r)
        {
            cur++;
            for(int j = 0;j < vt[cur].size();++j)
            {
                int tmp = vt[cur][j].first;
                int pos = vt[cur][j].second;
                if(vis[tmp]) add(vis[tmp],-1);
                vis[tmp]=pos;
                add(pos,1);
            }
        }
        ans[op[i].id] = sum(op[i].r)-sum(op[i].l-1);
    }
    for(int i = 1;i <= q;++i)
    printf("%dn",ans[i]);
}
int main()
{

    while(~scanf("%d %d",&n,&q))
    {
        init(); 
        for(int i = 1;i <= n;++i)
        scanf("%d",&a[i]);
        for(int i = 1;i <= q;++i)
        {
            scanf("%d %d",&op[i].l,&op[i].r);
            op[i].id = i;
        }
        sort(op+1,op+1+q);
        solve();
    }
    return 0;
}