[HDOJ5869] Different GCD Subarray Query（RMQ，树状数组，离线）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5869

题意：n个数，q次询问，问区间内gcd不同值的个数。

和dquery那道题一样，也是离线的做法。按照查询的r从小到大排序，每插入一个数字ai，则更新一次gcd，总是把gcd出现向后移动，这样可以满足靠后的查询能够包含住这些值。

首先用st表预处理出区间的gcd，而且观察到gcd单调不增的性质，在枚举区间gcd的值的时候，可以二分。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef struct Event {
 5     int l, r, id;
 6 }Event;
 7 const int maxn = 100100;
 8 int n, q, a[maxn];
 9 int dp[maxn][20];
10 int bit[maxn];
11 vector<Event> event;
12 int ret[maxn];
13 unordered_map<int, int> vis;
14 
15 bool cmp(Event a, Event b) { return a.r < b.r; }
16 int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
17 int lowbit(int x) { return x & (-x); }
18 void add(int i, int v) { for(; i <= n; i+=lowbit(i)) bit[i] += v; }
19 int sum(int i) { int ret = 0; for(; i > 0; i-=lowbit(i)) ret += bit[i]; return ret; }
20 int query(int l, int r) { int k = int(log(r-l+1.0)/log(2.0)); return gcd(dp[l][k], dp[r-(1<<k)+1][k]); }
21 
22 int main() {
23     // freopen("in", "r", stdin);
24     int l, r;
25     while(~scanf("%d%d",&n,&q)) {
26         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
27         event.clear(); vis.clear();
28         memset(bit, 0, sizeof(bit));
29         for(int i = 1; i <= n; i++) dp[i][0] = a[i];
30         int k = int(log(n+1.0)/log(2.0));
31         for(int j = 1; j <= k; j++) {
32             for(int i = 1; i + (1 << j) - 1 <= n; i++) {
33                 dp[i][j] = gcd(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
34             }
35         }
36         for(int i = 1; i <= q; i++) {
37             scanf("%d%d",&l,&r);
38             event.push_back(Event{l,r,i});
39         }
40         sort(event.begin(), event.end(), cmp);
41         int pos = 0;
42         for(int i = 1; i <= n; i++) {
43             int cur = a[i];
44             int j = i;
45             while(j >= 1) {
46                 int tmp = j;
47                 l = 1, r = j;
48                 while(l <= r) {
49                     int mid = (l + r) >> 1;
50                     if(l == r && query(mid, i) == cur) {
51                         tmp = mid;
52                         break;
53                     }
54                     if(query(mid, i) == cur) {
55                         tmp = mid;
56                         r = mid - 1;
57                     }
58                     else l = mid + 1;
59                 }
60                 if(vis.find(cur) == vis.end()) {
61                     add(j, 1);
62                     vis[cur] = j;
63                 }
64                 else if(vis[cur] < j) {
65                     add(vis[cur], -1);
66                     add(j, 1);
67                     vis[cur] = j;
68                 }
69                 j = tmp - 1;
70                 if(j >= 1) cur = query(j ,i);
71             }
72             while(pos < event.size() && event[pos].r == i) {
73                 ret[event[pos].id] = sum(event[pos].r) - sum(event[pos].l-1);
74                 pos++;
75             }
76         }
77         for(int i = 1; i <= q; i++) {
78             printf("%d
", ret[i]);
79         }
80     }
81     return 0;
82 }