## 【HDU-5869】Different GCD Subarray Query

【HDU – 5869】Different GCD Subarray Query

【2016 ACM/ICPC Asia Regional Dalian Online】

【gcd+离线查询+树状数组】

Solution:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
// #define DBG
using namespace std;

const int LIM = 1e5 + 10;
const int MAXI = 1e6 + 10;
struct query {
int l, r, idx;
bool operator < (const query & q) const {
return r < q.r;
}
} qs[LIM];
int data[LIM];
int bit[LIM];
int vis[MAXI];
int ans[LIM];
int n;
vector<pair<int, int> > gcds[LIM];

inline int gcd(int a, int b) {
return a % b ? (gcd(b, a % b)) : b;
}

inline int lowbit(int x) {
return x & (-x);
}

void add(int pos, int diff) {
while (pos < n) {
bit[pos] += diff;
pos += lowbit(pos);
}
}

int getSum(int pos) {
int ret = 0;
while (pos) {
ret += bit[pos];
pos -= lowbit(pos);
}
return ret;
}

int main(void) {
int q;
while (~scanf("%d%d", &n, &q)) {
for (int i = 1; i <= n; i++) {
scanf("%d", data + i);
gcds[i].clear();
}
/* discretization */
for (int i = 1; i <= n; i++) {
int g = data[i], lp = i;
for (int j = 0; j < gcds[i - 1].size(); j++) {
int tmpg = gcd(g, gcds[i - 1][j].first);
if (g != tmpg) {
gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
g = tmpg;
lp = gcds[i - 1][j].second;
}
}
gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
}
/* input the query and sort them */
for (int i = 0; i < q; i++) {

scanf("%d%d", &qs[i].l, &qs[i].r);
qs[i].idx = i;
}
sort(qs, qs + q);
/* operation of the binary index tree */
memset(vis, 0, sizeof vis);
memset(bit, 0, sizeof bit);
int pos = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < gcds[i].size(); j++) {
int g = gcds[i][j].first;
int lp = gcds[i][j].second;
vis[g] = lp;
}
while (qs[pos].r == i) {
ans[qs[pos].idx] = getSum(qs[pos].r) - getSum(qs[pos].l - 1);
pos++;
}
#ifdef DBG
printf("-----------------\n");
for (int i = 1; i <= 5; i++)
printf("%d: %d\n", i, bit[i]);
#endif
}
for (int i = 0; i < q; i++) {
printf("%d\n", ans[i]);
}
}
return 0;
}