Codeforces359 D. Pair of Numbers （二分+rmq(ST表) ）

63 阅读 0 评论 42 点赞

我是靠谱客的博主任性纸鹤，最近开发中收集的这篇文章主要介绍Codeforces359 D. Pair of Numbers （二分+rmq(ST表) ），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

给定长度为n的数组
要求找到若干对L和R，满足以下条件：

[L,R]内存在一个数，满足[L,R]的所有数能被这个数整除
使R-L尽量大

输出满足条件的(L,R)对数，以及最大的R-L
还需要输出所有满足条件的数对(L,R)的左端点L

数据范围：n<=3e5

解法：

观察问题条件1:
[L,R]内存在一个数，满足[L,R]的所有数能被这个数整除
想想能整除区间内所有数的数需要满足什么性质？
因为这个数需要能整除区间内所有数，且这个数需要在区间内
那么这个数一定就是这个区间内的最小数
因为这个数整除所有数，且这个数最小，那么这个区间的gcd就等于这个数

综上得满足条件的区间即满足:区间min=区间gcd

R-L尽量大等同于R-L+1尽量大，其实就是区间尽量大
如果存在长度为k的区间满足，那么一定存在长度为k-1的区间也满足
也就是说答案存在单调性，可以二分

二分区间长度然后尺取check就行了
区间min和区间gcd用rmq数据结构来计算就行了

code：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int m[N][25],g[N][25],maxd;
int lg2[N];
int a[N],n;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
void rmq_init(){
    lg2[1]=0;
    for(int i=2;i<N;i++){//预处理lg2[]
        lg2[i]=lg2[i-1];
        if((i&(i-1))==0)lg2[i]++;
    }
    maxd=lg2[n]+1;
    for(int i=1;i<=n;i++){
        m[i][0]=g[i][0]=a[i];
    }
    for(int j=1;j<=maxd;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]);
            g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
        }
    }
}
int m_ask(int l,int r){
    int k=lg2[r-l+1];
    return min(m[l][k],m[r-(1<<k)+1][k]);
}
int g_ask(int l,int r){
    int k=lg2[r-l+1];
    return gcd(g[l][k],g[r-(1<<k)+1][k]);
}
bool check(int mid){
    for(int i=1;i<=n;i++){
        int j=i+mid-1;
        if(j>n)break;
        if(m_ask(i,j)==g_ask(i,j)){
            return 1;
        }
    }
    return 0;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    rmq_init();
    int l=1,r=n;
    int ans=1;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    vector<int>idx;
    for(int i=1;i<=n;i++){
        int j=i+ans-1;
        if(j>n)break;
        if(m_ask(i,j)==g_ask(i,j)){
            idx.push_back(i);
        }
    }
    printf("%d %dn",(int)idx.size(),ans-1);
    for(int v:idx){
        printf("%d ",v);
    }
    return 0;
}