HDU 5869 Different GCD Subarray Query

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5869

题目翻译

给一个序列，求[L,R]区间内，有多少个不同的子区间的区间GCD

题解

首先计算不同的GCD，我们使用离线询问，然后用树状数组/线段树把不同数记录在最后一次出现位置的方法。
然后如何计算不同的GCD，则可以通过ST表+倍增 logN 的查找。

代码

/*
  Author : WNJXYK
  Problem : HDU 5869
  Blog : http://wnjxyk.cn
  Date : 2016
*/
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<map>
using namespace std;
const int Maxn=100000;
struct Query{
    int l,r;
    int index;
};
int ans[Maxn+5];
Query qey[Maxn+5];
int num[Maxn+5];
int n,q;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int st[Maxn+5][20];
inline void ST(int n){
    for (int i=1;i<=n;i++) st[i][0]=num[i];
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
}
int queryST(int left,int right){
    int k=0;
    while((1<<(k+1))<=right-left+1) k++;
    return gcd(st[left][k],st[right-(1<<k)+1][k]);
}
const int MaxNum=1000000;
int sum[MaxNum+5];
inline int lowbit(int x){
    return x&(-x);
}
inline int add(int x,int val){
    for (int i=x;i<=MaxNum;i+=lowbit(i))
        sum[i]+=val;
}
inline int get(int x){
    int ret=0;
    for (int i=x;i;i-=lowbit(i))
        ret+=sum[i];
    return ret;
}
inline bool cmpQey(Query a,Query b){
    if (a.r<b.r) return true;
    return false;
}
map<int,int> lastPos;
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&q)!=EOF){
        for (int i=1;i<=n;i++) scanf("%d",&num[i]);
        for (int i=1;i<=q;i++) scanf("%d%d",&qey[i].l,&qey[i].r);
        for (int i=1;i<=q;i++) qey[i].index=i;
        memset(sum,0,sizeof(sum));
        lastPos.clear();
        ST(n);
        sort(qey+1,qey+q+1,cmpQey);
        int nowQuery=1;
        int lm=0;
        while((1<<(lm+1))<=n) lm++;
        for (int r=1;r<=n;r++){
            int gcdNum=num[r],l=r;
            //printf("GCD = %d ( %d - ",gcdNum,r);
            if (lastPos[gcdNum]!=0){
                add(lastPos[gcdNum],-1);
                add(l,1);
            }else{
                add(l,1);
            }
            lastPos[gcdNum]=l;
            while(l>=1){
                for (int i=lm;i>=0;i--){
                    if (l-(1<<i)<=0) continue;
                    if (queryST(l-(1<<i),r)==gcdNum) l-=(1<<i);
                }
                //printf(" %d ) \n",l);
                l--;
                if (l>=1){
                    gcdNum=gcd(gcdNum,num[l]);
                    //printf("GCD = %d ( %d - ",gcdNum,l);
                    if (lastPos[gcdNum]!=0){
                        add(lastPos[gcdNum],-1);
                        add(l,1);
                    }else{
                        add(l,1);
                    }
                    lastPos[gcdNum]=l;
                }
            }
            while(nowQuery<=q && qey[nowQuery].r==r){
                ans[qey[nowQuery].index]=get(qey[nowQuery].r)-get(qey[nowQuery].l-1);
                nowQuery++;
            }
        }
        for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

Author : WNJXYK

Problem : HDU 5869

Blog : http://wnjxyk.cn

Date : 2016

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

#include<vector>

#include<map>

using namespace std;

const int Maxn=100000;

struct Query{

int l,r;

int index;

};

int ans[Maxn+5];

Query qey[Maxn+5];

int num[Maxn+5];

int n,q;

int gcd(int a,int b){

return b==0?a:gcd(b,a%b);

}

int st[Maxn+5][20];

inline void ST(int n){

for (int i=1;i<=n;i++) st[i][0]=num[i];

for (int j=1;(1<<j)<=n;j++)

for (int i=1;i+(1<<j)-1<=n;i++){

st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);

}

int queryST(int left,int right){

int k=0;

while((1<<(k+1))<=right-left+1) k++;

return gcd(st[left][k],st[right-(1<<k)+1][k]);

}

const int MaxNum=1000000;

int sum[MaxNum+5];

inline int lowbit(int x){

return x&(-x);

}

inline int add(int x,int val){

for (int i=x;i<=MaxNum;i+=lowbit(i))

sum[i]+=val;

}

inline int get(int x){

int ret=0;

for (int i=x;i;i-=lowbit(i))

ret+=sum[i];

return ret;

}

inline bool cmpQey(Query a,Query b){

if (a.r<b.r) return true;

return false;

}

map<int,int> lastPos;

int main(){

//freopen("in.txt","r",stdin);

while(scanf("%d%d",&n,&q)!=EOF){

for (int i=1;i<=n;i++) scanf("%d",&num[i]);

for (int i=1;i<=q;i++) scanf("%d%d",&qey[i].l,&qey[i].r);

for (int i=1;i<=q;i++) qey[i].index=i;

memset(sum,0,sizeof(sum));

lastPos.clear();

ST(n);

sort(qey+1,qey+q+1,cmpQey);

int nowQuery=1;

int lm=0;

while((1<<(lm+1))<=n) lm++;

for (int r=1;r<=n;r++){

int gcdNum=num[r],l=r;

//printf("GCD = %d ( %d - ",gcdNum,r);

if (lastPos[gcdNum]!=0){

add(lastPos[gcdNum],-1);

add(l,1);

}else{

add(l,1);

}

lastPos[gcdNum]=l;

while(l>=1){

for (int i=lm;i>=0;i--){

if (l-(1<<i)<=0) continue;

if (queryST(l-(1<<i),r)==gcdNum) l-=(1<<i);

}

//printf(" %d ) \n",l);

l--;

if (l>=1){

gcdNum=gcd(gcdNum,num[l]);

//printf("GCD = %d ( %d - ",gcdNum,l);

if (lastPos[gcdNum]!=0){

add(lastPos[gcdNum],-1);

add(l,1);

}else{

add(l,1);

}

lastPos[gcdNum]=l;

}

while(nowQuery<=q && qey[nowQuery].r==r){

ans[qey[nowQuery].index]=get(qey[nowQuery].r)-get(qey[nowQuery].l-1);

nowQuery++;

}

for (int i=1;i<=q;i++) printf("%d\n",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

WNJXYKの博客

喂你脚下有坑