HDU 5869 (离线+树状数组)

78 阅读 0 评论 52 点赞

我是靠谱客的博主精明小猫咪，最近开发中收集的这篇文章主要介绍HDU 5869 (离线+树状数组)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Different GCD Subarray Query

题目大意

　　给定n个数的序列，有q个询问，每次询问一个区间中所有子区间所形成不同的gcd的数量。

解题分析

　　由于固定一个数为右端点，所能形成的gcd共有logn，所以可以预处理出每个数为右端点所能形成的gcd，相同gcd取左端点靠右的。

　　然后将询问离线，按照r从小到大排序。处理gcd重复的方法是将相同的gcd值保留左端点较大的。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 100008             
19 #define M 1000008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const int INF = 2000000000;
30 /**************************************************************************/ 
31 int n,m;
32 int a[N],pre[N],last[M],ans[N];
33 struct node{
34     int x,id;
35 };
36 vector <node> q[N];
37 struct BIT{
38     int a[N];
39     void clear(){
40         clr(a,0);
41     }
42     void add(int x,int val){
43         for (int i=x;i<N;i+=i & (-i)) a[i]+=val;
44     }
45     int query(int x){
46         int res=0;
47         for (int i=x;i>0;i-=i & (-i)) res+=a[i];
48         return res;
49     }
50     int sigma(int l,int r){
51         return query(r)-query(l-1);
52     }
53 }T;
54 int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
55 int main(){
56     while (~scanf("%d%d",&n,&m)){
57         rep(i,1,n) scanf("%d",&a[i]);
58         rep(i,1,n) q[i].clear();
59         rep(i,1,m){
60             int l,r;
61             scanf("%d%d",&l,&r);
62             q[r].push_back((node){l,i});
63         }
64         repd(i,n,1)
65             pre[i]= a[i]==a[i-1]? pre[i-1] : i-1;
66         clr(last,0);
67         T.clear();
68         rep(i,1,n){
69             for (int j=i,x=a[j];j>0;j=pre[j],x=gcd(x,a[j])){
70                 if (j>last[x]){
71                     if (last[x]!=0) T.add(last[x],-1);
72                     T.add(j,1);
73                     last[x]=j;
74                 }
75                 if (x==1) break;
76             }
77             for (int j=0;j<q[i].size();j++){
78                 ans[q[i][j].id]=T.sigma(q[i][j].x,i);
79             }
80         }
81         rep(i,1,m) printf("%dn",ans[i]);
82     }
83 }