HDU 5869.Different GCD Subarray Query-区间gcd+树状数组 (神奇的标记右移操作) (2016年ICPC大连网络赛)...Different GCD Subarray Query

89 阅读 0 评论 59 点赞

我是靠谱客的博主斯文悟空，这篇文章主要介绍HDU 5869.Different GCD Subarray Query-区间gcd+树状数组 (神奇的标记右移操作) (2016年ICPC大连网络赛)...Different GCD Subarray Query，现在分享给大家，希望可以做个参考。

树状数组。。。

Different GCD Subarray Query

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1541 Accepted Submission(s): 599

Problem Description

This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:

Given an array

Input

There are several tests, process till the end of input.

For each test, the first line consists of two integers

Output

For each query, output the answer in one line.

Sample Input

5 3

1 3 4 6 9

3 5

2 5

1 5

Sample Output

Source

2016 ACM/ICPC Asia Regional Dalian Online

这个题的意思就是问区间内所有子段不同gcd的个数。

一开始理解错了题意，后来想明白了。假设区间的数为1 2 3 4

就是gcd(1),gcd(2),gcd(3),gcd(4),gcd(1,2),gcd(2,3),gcd(3,4),gcd(1,2,3),gcd(2,3,4),gcd(1,2,3,4)这些里面不同的gcd的个数是多少。

如果用在线算法操作，每查询一次就要处理依次数据，一方面会造成浪费，另一方面，你这样写妥妥的超时啊，所以要用离线算法，将所有的数据处理好之后，按顺序直接输出结果就可以。

首先用一个数组将数据保存起来，然后用一个vector数组将查询的区间和查询的顺序记录下来。

处理数据，就是相对来说固定右端点，从右往左移，在代码里就是对于每一个i(固定右端点)，遍历一下i所在的子段的gcd，因为i不变，j是上一个i的gcd的值保存的顺序，j越大，i所在的子段就依次向左增加一个数，如果gcd发生了变化，就记录一下这个gcd以及出现的位置。可能越说越乱，画一个图表示一下。。。

图的意思就是假设数据为2 4 9 6 5，i为下标。假设i为4，就是固定4，然后遍历j，j存的是上一个i的子段的gcd，通过上一个i的gcd来得到i为4时(6)的子段的gcd，图中画的横线的长度就是子段的长度，橙色的矩形包含的长度是上一个i处理出的数据。就是固定右端点，依次往左遍历得到所有的gcd，这样不会重复操作，也不会漏掉某个子段。

将gcd整理出来之后，怎么操作才能使得区间查询的是不同的gcd的个数呢？

对于区间内相同的gcd，让标记gcd的下标尽量右移，找该gcd的最大右端点。

通过树状数组维护gcd的下标。

一边维护，一边查询树状数组就可以保证数据正确。

总结一下就是:固定右端点，依次往左找出来所有的gcd，并标记下标，因为是i逐渐增大的，所以后面遍历的时候也是相同gcd的最大右端点。直接查询就可以。

就这样吧，不想好好写了。

代码:

复制代码

1 //离线处理-树状数组
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<vector>
10 #include<utility>
11 using namespace std;
12 const int maxn=1e5+10;
13 int Arr[maxn];//存数据一开始的值
14 int N,Q;
15 int pos[maxn*10]; //记录gcd的位置
16 vector<pair<int ,int> >querys[maxn];
17 vector<pair<int, int> >gcds[maxn];
18 int ans[maxn];
19 int treeArr[maxn]; //树状数组
20 
21 int gcd(int a,int b){ //gcd求最大公约数
22     if(!(a%b))return b;
23     else return gcd(b,a%b);
24 }
25 
26 void init(){ //初始化
27     int tmp,ts;
28     for(int i=1;i<=N;i++){
29         tmp=Arr[i];
30         ts=i;                                     //固定右端点，向左遍历
31         for(int j=0;j<gcds[i-1].size();j++){
32             int tmpgcd=gcd(tmp,gcds[i-1][j].first);
33             if(tmpgcd!=tmp){  //如果gcd发生变化
34                 gcds[i].push_back(make_pair(tmp,ts)); //first存gcd，second存gcd的左端点ts
35                 ts=gcds[i-1][j].second; //上一个gcd的右端点就是下一个gcd的左端点
36                 tmp=tmpgcd;
37             }
38         }
39         gcds[i].push_back(make_pair(tmp,ts)); //将与上一个的最左端的gcd存起来
40     }
41     return;
42 }
43 
44 int lowbit(int x){  //取最低位的1
45     return x&(-x);
46 }
47 
48 void Add(int cur,int num){ //单点更新
49     for(int i=cur;i<=N;i+=lowbit(i))
50         treeArr[i]+=num;   //由叶子节点向上更新树状数组
51     return;
52 }
53 
54 int Query(int cur){ //区间查询  从右端点往左加二进制最低位1的
55     int sum=0;
56     for(int i=cur;i>0;i-=lowbit(i))
57         sum+=treeArr[i];
58     return sum;
59 }
60 
61 void Solve(){
62     memset(pos,0,sizeof(pos));
63     memset(treeArr,0,sizeof(treeArr));
64     for(int i=1;i<=N;i++){
65         for(int j=0;j<gcds[i].size();j++){
66             if(pos[gcds[i][j].first]){ //如果标记已经存在，就将标记去掉，所以执行单点更新操作
67                 Add(pos[gcds[i][j].first],-1);
68             }
69             Add(gcds[i][j].second,1);//一个新的不同的gcd，从叶子节点开始更新个数+1
70             pos[gcds[i][j].first]=gcds[i][j].second;//记录该gcd的右端点
71         }
72         for(int j=0;j<querys[i].size();j++){
73             ans[querys[i][j].second]=Query(i)-Query(querys[i][j].first-1);//区间右端点-区间左区间
74         }
75     }
76     for(int i=1;i<=Q;i++)
77         printf("%dn",ans[i]);
78 
79     return;
80 }
81 int main(){
82     //reopen("input","r",stdin);
83     while(~scanf("%d%d",&N,&Q)){
84         for(int i=1;i<=N;i++){
85             scanf("%d",&Arr[i]); //将数据存在Arr数组中
86             querys[i].clear(); //清空
87             gcds[i].clear(); //清空
88         }
89         init();
90         int tmp1,tmp2;
91         for(int i=1;i<=Q;i++){
92             scanf("%d%d",&tmp1,&tmp2);
93             querys[tmp2].push_back(make_pair(tmp1,i)); //将tmp1与i成对插入vector的tmp2下标里
94         }
95         Solve();
96     }
97     return 0;
98 }

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
 1 //离线处理-树状数组
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<vector>
10 #include<utility>
11 using namespace std;
12 const int maxn=1e5+10;
13 int Arr[maxn];//存数据一开始的值
14 int N,Q;
15 int pos[maxn*10]; //记录gcd的位置
16 vector<pair<int ,int> >querys[maxn];
17 vector<pair<int, int> >gcds[maxn];
18 int ans[maxn];
19 int treeArr[maxn]; //树状数组
20 
21 int gcd(int a,int b){ //gcd求最大公约数
22     if(!(a%b))return b;
23     else return gcd(b,a%b);
24 }
25 
26 void init(){ //初始化
27     int tmp,ts;
28     for(int i=1;i<=N;i++){
29         tmp=Arr[i];
30         ts=i;                                     //固定右端点，向左遍历
31         for(int j=0;j<gcds[i-1].size();j++){
32             int tmpgcd=gcd(tmp,gcds[i-1][j].first);
33             if(tmpgcd!=tmp){  //如果gcd发生变化
34                 gcds[i].push_back(make_pair(tmp,ts)); //first存gcd，second存gcd的左端点ts
35                 ts=gcds[i-1][j].second; //上一个gcd的右端点就是下一个gcd的左端点
36                 tmp=tmpgcd;
37             }
38         }
39         gcds[i].push_back(make_pair(tmp,ts)); //将与上一个的最左端的gcd存起来
40     }
41     return;
42 }
43 
44 int lowbit(int x){  //取最低位的1
45     return x&(-x);
46 }
47 
48 void Add(int cur,int num){ //单点更新
49     for(int i=cur;i<=N;i+=lowbit(i))
50         treeArr[i]+=num;   //由叶子节点向上更新树状数组
51     return;
52 }
53 
54 int Query(int cur){ //区间查询  从右端点往左加二进制最低位1的
55     int sum=0;
56     for(int i=cur;i>0;i-=lowbit(i))
57         sum+=treeArr[i];
58     return sum;
59 }
60 
61 void Solve(){
62     memset(pos,0,sizeof(pos));
63     memset(treeArr,0,sizeof(treeArr));
64     for(int i=1;i<=N;i++){
65         for(int j=0;j<gcds[i].size();j++){
66             if(pos[gcds[i][j].first]){ //如果标记已经存在，就将标记去掉，所以执行单点更新操作
67                 Add(pos[gcds[i][j].first],-1);
68             }
69             Add(gcds[i][j].second,1);//一个新的不同的gcd，从叶子节点开始更新个数+1
70             pos[gcds[i][j].first]=gcds[i][j].second;//记录该gcd的右端点
71         }
72         for(int j=0;j<querys[i].size();j++){
73             ans[querys[i][j].second]=Query(i)-Query(querys[i][j].first-1);//区间右端点-区间左区间
74         }
75     }
76     for(int i=1;i<=Q;i++)
77         printf("%dn",ans[i]);
78 
79     return;
80 }
81 int main(){
82     //reopen("input","r",stdin);
83     while(~scanf("%d%d",&N,&Q)){
84         for(int i=1;i<=N;i++){
85             scanf("%d",&Arr[i]); //将数据存在Arr数组中
86             querys[i].clear(); //清空
87             gcds[i].clear(); //清空
88         }
89         init();
90         int tmp1,tmp2;
91         for(int i=1;i<=Q;i++){
92             scanf("%d%d",&tmp1,&tmp2);
93             querys[tmp2].push_back(make_pair(tmp1,i)); //将tmp1与i成对插入vector的tmp2下标里
94         }
95         Solve();
96     }
97     return 0;
98 }