hdu5869 Different GCD Subarray Query(rmq+树状数组+gcd)

115 阅读 0 评论 76 点赞

我是靠谱客的博主纯情柚子，这篇文章主要介绍hdu5869 Different GCD Subarray Query(rmq+树状数组+gcd)，现在分享给大家，希望可以做个参考。

题目链接：点这里！！！

题意：

给你n个数,q个询问，对于每个询问[l,r]问你[l,r]里面所有子集构成多少种不同的gcd？l1<=l2<=r2<=r1，([l2,r2]是[l1,r1]的子集)

数据范围：n,q<=100000 1<=a[i]<=1000000

题解：

比赛的时候傻逼了，用莫队去做，结果各种超时。。

赛后看了题解想了一下，发现其实用用树状数组就可以了，傻逼了。。

这道题我们对所有询问按右端点排序，然后离线来处理！

我们发现固定右端点向左gcd，最多有20段不同的gcd(因为2^20>1e6)。我们可以利用rmq+gcd处理出来，并且记录每段gcd的值及其最右端的下标！！

然后我们从左往右遍历，对于每个x，我们去枚举他向右的gcd，然后对于不同的gcd去更新，对于gcd==x,我们记录gcd为x最右边的下标，在当前下标+1，之前的地方-1就ok啦！

对于每个gcd我们记录都是最右的，我们再利用树状数组求和就可以了！！！

代码：

复制代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#include<cmath>
#define pb push_back
#define pa pair<int,int>
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define bug(x) printf("%d++++++++++++++++++++%dn",x,x)
#define key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:102400000000,102400000000")
typedef
long long LL;
const LL
MOD = 1000000007;
const int N = 1e5+15;
const int maxn = 1e6+15;
const int letter = 130;
const int INF = 2e9+15;
const double pi=acos(-1.0);
const double eps=1e-13;
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,q,a[N],xx[N][20],x[N][20],xid[N];
int f[N],vis[maxn],ans[N];
struct node{
int l,r,id;
bool operator < (const node &p)const{
return r<p.r;
}
}que[N];
int mm[N],dp[N][20];
int lowbit(int x){return x&(-x);}
void add(int x,int val){
if(x==0) return;
while(x<N){f[x]+=val,x+=lowbit(x);}
}
int query(int x){
int ans=0;
while(x>0){ans+=f[x],x-=lowbit(x);}
return ans;
}
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
void initrmq(int n,int a[]){
mm[0]=-1;
for(int i=1;i<=n;i++){
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
dp[i][0]=a[i];
}
for(int j=1;j<=mm[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++){
dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int rmq(int x,int y){
int k=mm[y-x+1];
return gcd(dp[x][k],dp[y-(1<<k)+1][k]);
}
void init(){
clr(vis,0),clr(f,0),clr(xid,0);
initrmq(n,a);
}
int main(){
while(~scanf("%d%d",&n,&q)){
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=q;i++){
que[i].id=i;
scanf("%d%d",&que[i].l,&que[i].r);
}
init();
for(int i=1;i<=n;i++){
int l=1,r=i,mid,vs,ans,pp;
while(1){
ans=pp=r;
vs=rmq(r,i);
xx[i][xid[i]]=vs,x[i][xid[i]++]=ans;
while(l<=r){
mid=(l+r)>>1;
if(rmq(mid,i)<vs) l=mid+1;
else ans=mid,r=mid-1;
}
l=1,r=ans-1;
if(l>r) break;
}
}
sort(que+1,que+q+1);
int r=1;
for(int i=1;i<=q;i++){
for(;r<=que[i].r;r++){
for(int j=0;j<xid[r];j++){
if(x[r][j]>vis[xx[r][j]]){
add(vis[xx[r][j]],-1);
add(x[r][j],1);
vis[xx[r][j]]=x[r][j];
}
}
}
ans[que[i].id]=query(que[i].r)-query(que[i].l-1);
}
for(int i=1;i<=q;i++) printf("%dn",ans[i]);
}
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#include<cmath>
#define pb push_back
#define pa pair<int,int>
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define bug(x) printf("%d++++++++++++++++++++%dn",x,x)
#define key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:102400000000,102400000000")
typedef
long long LL;
const LL
MOD = 1000000007;
const int N = 1e5+15;
const int maxn = 1e6+15;
const int letter = 130;
const int INF = 2e9+15;
const double pi=acos(-1.0);
const double eps=1e-13;
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,q,a[N],xx[N][20],x[N][20],xid[N];
int f[N],vis[maxn],ans[N];
struct node{
int l,r,id;
bool operator < (const node &p)const{
return r<p.r;
}
}que[N];
int mm[N],dp[N][20];
int lowbit(int x){return x&(-x);}
void add(int x,int val){
if(x==0) return;
while(x<N){f[x]+=val,x+=lowbit(x);}
}
int query(int x){
int ans=0;
while(x>0){ans+=f[x],x-=lowbit(x);}
return ans;
}
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
void initrmq(int n,int a[]){
mm[0]=-1;
for(int i=1;i<=n;i++){
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
dp[i][0]=a[i];
}
for(int j=1;j<=mm[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++){
dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int rmq(int x,int y){
int k=mm[y-x+1];
return gcd(dp[x][k],dp[y-(1<<k)+1][k]);
}
void init(){
clr(vis,0),clr(f,0),clr(xid,0);
initrmq(n,a);
}
int main(){
while(~scanf("%d%d",&n,&q)){
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=q;i++){
que[i].id=i;
scanf("%d%d",&que[i].l,&que[i].r);
}
init();
for(int i=1;i<=n;i++){
int l=1,r=i,mid,vs,ans,pp;
while(1){
ans=pp=r;
vs=rmq(r,i);
xx[i][xid[i]]=vs,x[i][xid[i]++]=ans;
while(l<=r){
mid=(l+r)>>1;
if(rmq(mid,i)<vs) l=mid+1;
else ans=mid,r=mid-1;
}
l=1,r=ans-1;
if(l>r) break;
}
}
sort(que+1,que+q+1);
int r=1;
for(int i=1;i<=q;i++){
for(;r<=que[i].r;r++){
for(int j=0;j<xid[r];j++){
if(x[r][j]>vis[xx[r][j]]){
add(vis[xx[r][j]],-1);
add(x[r][j],1);
vis[xx[r][j]]=x[r][j];
}
}
}
ans[que[i].id]=query(que[i].r)-query(que[i].l-1);
}
for(int i=1;i<=q;i++) printf("%dn",ans[i]);
}
return 0;
}