Codeforces 475D 题解(二分查找+ST表)

题面:

传送门:http://codeforces.com/problemset/problem/475/D

Given a sequence of integers a1, …, an and q queries x1, …, xq on it. For each query xi you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, …, ar) = xi.

题目大意:

对于n个数的序列,给出q个询问,问有多少个区间满足区间最大公约数为x

分析:

求区间最大公约数很简单,可以利用Sparse-Table算法O(nlog2n)" role="presentation" style="position: relative;">O(nlog2n)O(nlog2n)预处理,O(1)" role="presentation" style="position: relative;">O(1)O(1)查询

我们只要把标准的ST表的递推公式改一下就可以了

st[i][j]=gcd(st[i][j−1],st[i+2j−1][j−1]" role="presentation" style="position: relative;">st[i][j]=gcd(st[i][j−1],st[i+2j−1][j−1]st[i][j]=gcd(st[i][j−1],st[i+2j−1][j−1]

最暴力的方法是直接枚举所有区间gcd值,再求区间个数,然后将x对应的区间个数保存在一个哈希表中,这种算法时间复杂度为O(n2)" role="presentation" style="position: relative;">O(n2)O(n2),实际上考虑到STL的map使用红黑树实现,查询为O(log2n)" role="presentation" style="position: relative;">O(log2n)O(log2n),时间复杂度还会更高

从枚举的过程中我们可以发现,固定区间左端点l,枚举右端点r时,很多区间的gcd值是和上一个区间相同的,导致这一次枚举是重复且无用的.因此,我们应该用更高效的方法去枚举区间.

因此,我们用二分查找去枚举gcd每次变化的位置,假设变化的位置为k(即gcd([l,k])!=gcd(l,k+1),则值为gcd([l,k])的区间个数会增加k-l+1个.这样重复枚举的情况会被消除.

由数论知识得左端点固定,随着右端点右移,gcd会变化log2n" role="presentation" style="position: relative;">log2nlog2n次!

(区间gcd的值必须是ai的因数，而且每次减少至少要除2(少了一个公因数,最小是2))

所以总时间复杂度为O(nlog2n)" role="presentation" style="position: relative;">O(nlog2n)O(nlog2n)

代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

#define maxn 100005

#define maxlog 32

#define INF 10000005

using namespace std;

int a[maxn];

inline int gcd(int a,int b) {

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

}

struct sparse_table {//ST表

    int st[maxn][maxlog];

    void init(int *a,int n) {

        for(int i=1; i<=n; i++) st[i][0]=a[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 query(int l,int r) {

        if(l==r) return st[l][0];

        int k=log2(r-l+1);

        return gcd(st[l][k],st[r-(1<<k)+1][k]);

    }

};

int n,q;

sparse_table gcda;

map<int,long long>ans;//预处理答案

int bin_search(int L,int R,int sta,int v){//二分查找区间gcd变化的位置的前一位

    int l=L,r=R;

    int ans=INF;

    while(l<=r){

        int mid=(l+r)>>1;

        if(gcda.query(sta,mid)==v){

            l=mid+1;

        }else{

            r=mid-1;

            ans=min(ans,mid-1);

        }

    }

    if(ans==INF) return r;

    else return ans;

}

int main() {

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

    scanf("%d",&n);

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

    gcda.init(a,n);

    ans.clear();

    int now_gcd,now_pos;

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

        now_gcd=a[i];

        now_pos=i;

        while(1) {

            int pre_pos=now_pos;//原来的位置

            now_pos=bin_search(pre_pos,n,i,now_gcd);//变化的位置,下一个数gcd不同

            now_gcd=gcda.query(i,now_pos);//原来的gcd

            ans[now_gcd]+=now_pos-pre_pos+1;//更新答案

            if(now_pos<n) {

                now_pos++;//左端点移动到下一个数,开始枚举新区间

                now_gcd=gcda.query(i,now_pos);//更新新的gcd

            } else break;

        }

    }

    scanf("%d",&q);

    int x;

    while(q--) {

        scanf("%d",&x);

        printf("%I64d\n",ans[x]);

    }

}

巴特西

Codeforces 475D 题解(二分查找+ST表)

题面:

分析:

代码:

最新文章

热门文章