Different GCD Subarray Query（离线+线段树）

107 阅读 0 评论 71 点赞

我是靠谱客的博主聪明酒窝，这篇文章主要介绍Different GCD Subarray Query（离线+线段树），现在分享给大家，希望可以做个参考。

https://cn.vjudge.net/problem/HDU-5869

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 a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].

Input

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

For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.

You can assume that

    1≤N,Q≤100000

   1≤ai≤1000000

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

题意：n个数，m个询问，每次询问一段区间的不同gcd的个数。

思路：这道题很明显离线做容易一些,因为我们在知道以a[i-1]为结尾的所有gcd时，就可以推出所有以a[i]为结尾的gcd，所以我们可以用个滚动set来存储以a[i-1]为结尾的所有gcd和以a[i]为结尾的所有gcd

当我们处理到以a[i]为结尾时，就把所有右端点为i的查询都给求出来，怎么求呢？

每一个gcd都是由一段区间求gcd得到的，那么每个gcd都有起始位置，即这段区间的左端点，而这个起始位置越靠右越好，这样在计算的时候就不会漏了，所以我们用unordered_map记录gcd的处理到a[i]最大起始位置

也就是说每个gcd都对应一个位置（一个位置可能对应多个gcd），那么在[l,r]这个区间的位置被标记了几次，就有多少个gcd

对于每个gcd的最大起始位置发生改变时，把原位置的标记数目-1，新位置的标记数目+1

单点更新区间查询，用线段树搞一搞就可以了

复制代码

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
set<int> se[2];
set<int>::iterator it;
unordered_map<int,int> mp;
int tr[N<<2];
void build(int l,int r,int p){
	if(l==r){
		tr[p]=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    tr[p]=tr[p<<1]+tr[p<<1|1];
}
void update(int l,int r,int p,int pos,int val){
	if(l==r){
		tr[p]+=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(l,mid,p<<1,pos,val);
	else update(mid+1,r,p<<1|1,pos,val);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
int query(int l,int r,int p,int ql,int qr){
	if(l==ql&&r==qr) return tr[p];
	int mid=(l+r)>>1;
	if(qr<=mid) return query(l,mid,p<<1,ql,qr);
	else if(ql>mid) return query(mid+1,r,p<<1|1,ql,qr);
	else return query(l,mid,p<<1,ql,mid)+query(mid+1,r,p<<1|1,mid+1,qr);
}
int a[N],tot=0;
struct node{
	int l,r,id,num;
}ans[N*10];
vector<node> v[N];
bool cmp(node a,node b){
	return a.id<b.id;
}
int main(){
	int n,q;
    while(~scanf("%d%d",&n,&q)){
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    		v[i].clear();
		}
		tot=0;
		se[0].clear();
		se[1].clear();
		mp.clear();
		build(1,n,1);
		for(int i=1;i<=q;i++) {
			int l,r;
			scanf("%d%d",&l,&r);
			v[r].push_back(node{l,r,i,0}); 
		}
		int p=0;
		for(int i=1;i<=n;i++){
			p^=1;
			se[p].clear();
			se[p].insert(a[i]);
			if(i>mp[a[i]]){
				if(mp[a[i]]) update(1,n,1,mp[a[i]],-1);
				mp[a[i]]=i;	
				update(1,n,1,mp[a[i]],1);
			}
			for(it=se[p^1].begin();it!=se[p^1].end();++it){
				int g=__gcd(a[i],*it);
				se[p].insert(g);
			    if(mp[g]<mp[*it]){
			    	if(mp[g]) update(1,n,1,mp[g],-1);
			    	mp[g]=mp[*it];
			    	update(1,n,1,mp[g],1);
				}
			}
			for(int j=0;j<v[i].size();j++){
				int l=v[i][j].l;
				int r=i;
				int id=v[i][j].id;
				int num=query(1,n,1,l,r);
				ans[++tot]=node{l,r,id,num};
			}
		}	
		sort(ans+1,ans+1+tot,cmp);
		for(int i=1;i<=tot;i++) printf("%dn",ans[i].num);
	}  
	return 0;
}

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
#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
set<int> se[2];
set<int>::iterator it;
unordered_map<int,int> mp;
int tr[N<<2];
void build(int l,int r,int p){
	if(l==r){
		tr[p]=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    tr[p]=tr[p<<1]+tr[p<<1|1];
}
void update(int l,int r,int p,int pos,int val){
	if(l==r){
		tr[p]+=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(l,mid,p<<1,pos,val);
	else update(mid+1,r,p<<1|1,pos,val);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
int query(int l,int r,int p,int ql,int qr){
	if(l==ql&&r==qr) return tr[p];
	int mid=(l+r)>>1;
	if(qr<=mid) return query(l,mid,p<<1,ql,qr);
	else if(ql>mid) return query(mid+1,r,p<<1|1,ql,qr);
	else return query(l,mid,p<<1,ql,mid)+query(mid+1,r,p<<1|1,mid+1,qr);
}
int a[N],tot=0;
struct node{
	int l,r,id,num;
}ans[N*10];
vector<node> v[N];
bool cmp(node a,node b){
	return a.id<b.id;
}
int main(){
	int n,q;
    while(~scanf("%d%d",&n,&q)){
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    		v[i].clear();
		}
		tot=0;
		se[0].clear();
		se[1].clear();
		mp.clear();
		build(1,n,1);
		for(int i=1;i<=q;i++) {
			int l,r;
			scanf("%d%d",&l,&r);
			v[r].push_back(node{l,r,i,0}); 
		}
		int p=0;
		for(int i=1;i<=n;i++){
			p^=1;
			se[p].clear();
			se[p].insert(a[i]);
			if(i>mp[a[i]]){
				if(mp[a[i]]) update(1,n,1,mp[a[i]],-1);
				mp[a[i]]=i;	
				update(1,n,1,mp[a[i]],1);
			}
			for(it=se[p^1].begin();it!=se[p^1].end();++it){
				int g=__gcd(a[i],*it);
				se[p].insert(g);
			    if(mp[g]<mp[*it]){
			    	if(mp[g]) update(1,n,1,mp[g],-1);
			    	mp[g]=mp[*it];
			    	update(1,n,1,mp[g],1);
				}
			}
			for(int j=0;j<v[i].size();j++){
				int l=v[i][j].l;
				int r=i;
				int id=v[i][j].id;
				int num=query(1,n,1,l,r);
				ans[++tot]=node{l,r,id,num};
			}
		}	
		sort(ans+1,ans+1+tot,cmp);
		for(int i=1;i<=tot;i++) printf("%dn",ans[i].num);
	}  
	return 0;
}