hdu 5869 Different GCD Subarray Query 预处理 + 离线

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
//  hdu 5869 Different GCD Subarray Query 预处理 + 离线
//
//  题目链接：
//
//      http://acm.split.hdu.edu.cn/showproblem.php?pid=5869
//
//  题目大意：
//
//      给定数组，求[L,R]段中所有子段的不同gcd的种类
//
//  解题思路：
//
//      根据XJ的题解，固定左端点的不同GCD的值，这个值是不超过logA
//  这样，我们可以预处理出对于当前a{i}，求出[1,i-1]的gcd值，然后
//  将查询按照右端点排个序，固定右端点，用树状数组求出[L，i]的gcd
//  的个数。当然，我们必须每次加入gcd到最右边界，因为只有最右边界
//  是最小的区间，在最右边界之前的区间都可以去到这个gcd的值。所以
//  用个vis数组存储边界
//
//  感悟：
//
//      这类题以前没有接触过，所以，当看到XJ的题解的时候，整个人处
//  于懵X状态，研究了差不多一个小时吧（ok，说实话是取得min），看着
//  代码还是挺亲切的，预处理还挺好理解的，之后的按右边界，可以放入
//  vector中，省去排序的时间，只是因为各种手残，GG一下午。继续努力
//  ^_^

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 8;

int a[MAXN];
int ans[MAXN];
vector<pii> gc[MAXN];
vector<pii> query[MAXN];

int vis[MAXN * 10];
int n,q;


struct SegmentTree{

#define lowbit(x) (x & (-x))
    int sum[MAXN];

    void init(){
        memset(sum,0,sizeof(sum));
    }

    void update(int x,int v){
        while(x <= n){
            sum[x] += v;
            x += lowbit(x);
        }
    }

    int getSum(int x){
        int ans = 0;
        while(x){
            ans += sum[x];
            x -= lowbit(x);
        }
        return ans;
    }
}it;

void init(){
    for (int i = 0;i <= n;i ++){
        gc[i].clear();
        query[i].clear();
    }
    memset(vis,0,sizeof(vis));
    it.init();
}

void input(){
    for (int i = 1;i <= n;i ++)
        scanf("%d",a + i);

    for (int i = 1;i <= n;i ++){
        int x = a[i];
        int y = i;

        for (int j = 0; j < gc[i - 1].size();j ++){
            int res = __gcd(gc[i - 1][j].first,x);
            if (x != res){
                gc[i].push_back(make_pair(x,y));
                x = res;

                y = gc[i - 1][j].second;
            }
        }

        gc[i].push_back(make_pair(x,y));
    }

    for (int i = 1;i <= q;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        query[r].push_back(make_pair(l,i));
    }

    for (int i = 1;i <= n;i ++){

        for (int j = 0;j < gc[i].size();j ++){
            int res = gc[i][j].first;
            int ind = gc[i][j].second;

            if (vis[res])
                it.update(vis[res],-1);
            vis[res] = ind;
            it.update(ind,1);
        }

        for (int j = 0;j < query[i].size();j ++){
            int l = query[i][j].first;
            int ind = query[i][j].second;

            ans[ind] = it.getSum(i) - it.getSum(l - 1);

        }

    }

    for (int i = 1;i <= q;i++){
        printf("%dn",ans[i]);
    }
}

int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        init();
        input();
    }
    return 0;
}