FZU 2224 An exciting GCD problem(GCD种类预处理+树状数组维护)同hdu5869

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2224
  1 //#pragma comment(linker, "/STACK:102400000, 102400000")
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <vector>
  8 #include <cmath>
  9 #include <ctime>
 10 #include <list>
 11 #include <set>
 12 #include <map>
 13 using namespace std;
 14 typedef long long LL;
 15 typedef pair <int, int> P;
 16 const int N = 1e6 + 5;
 17 int a[N/10 + 5], bit[N]; //_pos存的是gcd上一次出现的位置
 18 vector <P> ans[N/10 + 5]; //存的是以i为右端点的gcd
 19 map <int, int> _pos;
 20 struct query {
 21     int l, r, pos;
 22     bool operator <(const query& cmp) const {
 23         return r < cmp.r;
 24     }
 25 }q[N/10 + 5];
 26 int res[N/10 + 5]; //答案
 27 
 28 void init(int n) {
 29     _pos.clear();
 30     memset(bit, 0, sizeof(bit));
 31     for(int i = 1; i <= n; ++i) {
 32         ans[i].clear();
 33     }
 34 }
 35 
 36 int GCD(int a, int b) {
 37     return b ? GCD(b, a % b): a;
 38 }
 39 
 40 void add(int i, int x) {
 41     for( ; i <= N; i += (i&-i))
 42         bit[i] += x;
 43 }
 44 
 45 int sum(int i) {
 46     int s = 0;
 47     for( ; i >= 1; i -= (i&-i))
 48         s += bit[i];
 49     return s;
 50 }
 51 
 52 int main()
 53 {
 54     int n, m, t;
 55     scanf("%d", &t);
 56     while(t--) {
 57         scanf("%d %d", &n, &m);
 58         init(n);
 59         for(int i = 1; i <= n; ++i) {
 60             scanf("%d", a + i);
 61         }
 62         for(int i = 1; i <= m; ++i) {
 63             scanf("%d %d", &q[i].l, &q[i].r);
 64             q[i].pos = i;
 65         }
 66         for(int i = 1; i <= n; ++i) {
 67             int x = a[i], y = i;
 68             for(int j = 0; j < ans[i - 1].size(); ++j) {
 69                 int gcd = GCD(x, ans[i - 1][j].first);
 70                 if(gcd != x) {
 71                     ans[i].push_back(make_pair(x, y));
 72                     x = gcd, y = ans[i - 1][j].second;
 73                 }
 74             }
 75             ans[i].push_back(make_pair(x, y));
 76         }
 77         sort(q + 1, q + m + 1);
 78         int p = 1;
 79         for(int i = 1; i <= n; ++i) {
 80             for(int j = 0; j < ans[i].size(); ++j) {
 81                 if(!_pos[ans[i][j].first]) {
 82                     add(ans[i][j].second, 1);
 83                     _pos[ans[i][j].first] = ans[i][j].second;
 84                 } else {
 85                     add(_pos[ans[i][j].first], -1);
 86                     _pos[ans[i][j].first] = ans[i][j].second;
 87                     add(ans[i][j].second, 1);
 88                 }
 89             }
 90             while(i == q[p].r && p <= m) {
 91                 res[q[p].pos] = sum(q[p].r) - sum(q[p].l - 1);
 92                 ++p;
 93             }
 94         }
 95         for(int i = 1; i <= m; ++i) {
 96             printf("%d
", res[i]);
 97         }
 98     }
 99     return 0;
100 }