HDU5869 Different GCD Subarray Query(线段树&&离线处理)

116 阅读 0 评论 77 点赞

我是靠谱客的博主飞快黑猫，这篇文章主要介绍HDU5869 Different GCD Subarray Query(线段树&&离线处理)，现在分享给大家，希望可以做个参考。

题目：

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

题意：

找区间内所有子串GCD的个数

思路：

线段树离线搞搞，区间GCD收敛的很快，所以直接暴力预处理出到每个数字截至的后缀串有哪些GCD以及它们的位置，就是每个数字向前看有哪些GCD出现，这个数量是很少的。扫一遍然后离线询问，对于每个询问按照右端点排序。找到每个位置的时候把这个位置向前看的所有GCD的位置更新到pos[]里，pos[]存的就是每个gcd最后出现的位置，然后对于右端点在当前位置的询问线段树找一下pos[]在这个区间内的和就是答案了。

代码：

复制代码

//kopyh
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 112345
using namespace std;
int n,m,sum,res,flag;
#define root 1 , n , 1
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
struct node
{
    int pos,val;
    node(int x=0,int y=0){pos=x,val=y;}
    friend bool operator < (node a, node b)
    {
        return a.val < b.val;
    }
    friend node operator + (node a, node b)
    {
        return  node(a.pos,a.val+b.val);
    }
}arr[N<<2];
int add[N<<2],tot;
void pushUp(int rt)
{
    arr[rt] = arr[rt<<1]+arr[rt<<1|1];
}
void pushDown(int l,int r,int rt)
{
    if(add[rt])
    {
        int m = (l+r)>>1;
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        arr[rt<<1].val += (m-l+1)*add[rt];
        arr[rt<<1|1].val += (r-m)*add[rt];
        add[rt] = 0;
    }
}
void updata(int l,int r,int rt,int ql,int qr,int val)
{
    if(l>qr||ql>r)return;
    if(l>=ql&&r<=qr)
    {
        arr[rt].val += (r-l+1)*val;
        add[rt] += val;
        return;
    }
    pushDown(l,r,rt);
    int m = (l+r)>>1;
    if(ql<=m)updata(lson,ql,qr,val);
    if(qr>m)updata(rson,ql,qr,val);
    pushUp(rt);
}
void build(int l,int r,int rt)
{
    add[rt]=0;
    if(l == r)
    {
        arr[rt].val = 0;
        arr[rt].pos = tot;
        return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    pushUp(rt);
}
node query(int l,int r,int rt,int ql,int qr)
{
    if(l>qr||ql>r)
        return node(0,0);
    if(l>=ql&&r<=qr)
        return arr[rt];
    pushDown(l,r,rt);
    int m = (l+r)>>1;
    return query(lson,ql,qr)+query(rson,ql,qr);
}
int a[N],pos[N*10],ans[N];
vector<pair<int,int> >vc[N],qu[N];
int gcd(int x,int y)
{   return y?gcd(y,x%y):x;  }
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("test.txt","r",stdin);
    #endif
    int i,j,k,cas,T,t,x,y,z,now;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            vc[i].clear();
            qu[i].clear();
        }
        for(i=1;i<=n;i++)
        {
            x=a[i]; y=i;
            for(j=0;j<vc[i-1].size();j++)
            {
                t = gcd(vc[i-1][j].first,a[i]);
                if(t!=x)
                {
                    vc[i].push_back(make_pair(x,y));
                    x=t; y=vc[i-1][j].second;
                }
            }
            vc[i].push_back(make_pair(x,y));
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            qu[y].push_back(make_pair(x,i));
        }
        memset(pos,0,sizeof(pos));
        build(root);
        for(i=1;i<=n;i++)
        {
            for(j=0;j<vc[i].size();j++)
                if(pos[vc[i][j].first] < vc[i][j].second)
                {
                    if(pos[vc[i][j].first])updata(root,pos[vc[i][j].first],pos[vc[i][j].first],-1);
                    updata(root,vc[i][j].second,vc[i][j].second,1);
                    pos[vc[i][j].first] = vc[i][j].second;
//                    printf("pos=%d %dn",vc[i][j].first,pos[vc[i][j].first]);
                }
            for(j=0;j<qu[i].size();j++)
                ans[qu[i][j].second] = query(root,qu[i][j].first,i).val;
        }
        for(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
127
128
129
130
131
132
133
134
135
136
//kopyh
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 112345
using namespace std;
int n,m,sum,res,flag;
#define root 1 , n , 1
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
struct node
{
    int pos,val;
    node(int x=0,int y=0){pos=x,val=y;}
    friend bool operator < (node a, node b)
    {
        return a.val < b.val;
    }
    friend node operator + (node a, node b)
    {
        return  node(a.pos,a.val+b.val);
    }
}arr[N<<2];
int add[N<<2],tot;
void pushUp(int rt)
{
    arr[rt] = arr[rt<<1]+arr[rt<<1|1];
}
void pushDown(int l,int r,int rt)
{
    if(add[rt])
    {
        int m = (l+r)>>1;
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        arr[rt<<1].val += (m-l+1)*add[rt];
        arr[rt<<1|1].val += (r-m)*add[rt];
        add[rt] = 0;
    }
}
void updata(int l,int r,int rt,int ql,int qr,int val)
{
    if(l>qr||ql>r)return;
    if(l>=ql&&r<=qr)
    {
        arr[rt].val += (r-l+1)*val;
        add[rt] += val;
        return;
    }
    pushDown(l,r,rt);
    int m = (l+r)>>1;
    if(ql<=m)updata(lson,ql,qr,val);
    if(qr>m)updata(rson,ql,qr,val);
    pushUp(rt);
}
void build(int l,int r,int rt)
{
    add[rt]=0;
    if(l == r)
    {
        arr[rt].val = 0;
        arr[rt].pos = tot;
        return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    pushUp(rt);
}
node query(int l,int r,int rt,int ql,int qr)
{
    if(l>qr||ql>r)
        return node(0,0);
    if(l>=ql&&r<=qr)
        return arr[rt];
    pushDown(l,r,rt);
    int m = (l+r)>>1;
    return query(lson,ql,qr)+query(rson,ql,qr);
}
int a[N],pos[N*10],ans[N];
vector<pair<int,int> >vc[N],qu[N];
int gcd(int x,int y)
{   return y?gcd(y,x%y):x;  }
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("test.txt","r",stdin);
    #endif
    int i,j,k,cas,T,t,x,y,z,now;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            vc[i].clear();
            qu[i].clear();
        }
        for(i=1;i<=n;i++)
        {
            x=a[i]; y=i;
            for(j=0;j<vc[i-1].size();j++)
            {
                t = gcd(vc[i-1][j].first,a[i]);
                if(t!=x)
                {
                    vc[i].push_back(make_pair(x,y));
                    x=t; y=vc[i-1][j].second;
                }
            }
            vc[i].push_back(make_pair(x,y));
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            qu[y].push_back(make_pair(x,i));
        }
        memset(pos,0,sizeof(pos));
        build(root);
        for(i=1;i<=n;i++)
        {
            for(j=0;j<vc[i].size();j++)
                if(pos[vc[i][j].first] < vc[i][j].second)
                {
                    if(pos[vc[i][j].first])updata(root,pos[vc[i][j].first],pos[vc[i][j].first],-1);
                    updata(root,vc[i][j].second,vc[i][j].second,1);
                    pos[vc[i][j].first] = vc[i][j].second;
//                    printf("pos=%d %dn",vc[i][j].first,pos[vc[i][j].first]);
                }
            for(j=0;j<qu[i].size();j++)
                ans[qu[i][j].second] = query(root,qu[i][j].first,i).val;
        }
        for(i=1;i<=m;i++)
            printf("%dn",ans[i]);
    }
    return 0;
}