CodeForces 359 D.Pair of Numbers （二分+ST）

62 阅读 0 评论 41 点赞

我是靠谱客的博主俏皮钥匙，最近开发中收集的这篇文章主要介绍CodeForces 359 D.Pair of Numbers （二分+ST），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
给出长度为n的序列a[i]，要求找到所有满足下列两个条件的子序列a[l],a[l+1],…,a[r]的个数：
1.存在l<=j<=r，使得a[j]是a[l],a[l+1],…,a[r]的最大公因数
2.在所有满足1的子序列中取r-l最长的
Input
第一行一整数n表示序列长度，之后n个整数a[i]表示该序列(1<=n<=3e5,1<=a[i]<=1e6)
Output
首先输出子序列个数和长度，之后输出所有满足条件子序列的起始编号
Sample Input
5
4 6 9 3 6
Sample Output
1 3
2
Solution
一个子序列满足条件的当且仅当这个子序列的gcd和这个子序列的min是相同的，所以用ST表维护下区间gcd和区间min，然后二分子序列长度，对于一个二分值暴力去判断每个这个长度的子序列是否满足gcd和min相同（每个子序列的判断是O(1)的），时间复杂度O(nlogn)
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 333333
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int m[maxn][22],g[maxn][22],n,a[maxn],res,ans[maxn],temp[maxn];
void ST()
{
    for(int i=0;i<n;i++)g[i][0]=m[i][0]=a[i];
    int k=(int)(log(1.0*n)/log(2.0));
    for(int j=1;j<=k;j++)   
        for(int i=0;i+(1<<j)<=n;i++)  
            g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]),
            m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]); 
}
int query_gcd(int l,int r)  
{  
    int k=(int)(log(1.0*(r-l+1))/log(2.0));  
    return gcd(g[l][k],g[r-(1<<k)+1][k]);
}
int query_min(int l,int r)  
{  
    int k=(int)(log(1.0*(r-l+1))/log(2.0));  
    return min(m[l][k],m[r-(1<<k)+1][k]);
}
bool check(int mid)
{
    int cnt=0;
    for(int l=0;l+mid<n;l++)
        if(query_min(l,l+mid)==query_gcd(l,l+mid))
            temp[cnt++]=l+1;
    if(cnt)
    {
        res=cnt;
        for(int i=0;i<cnt;i++)ans[i]=temp[i];
        return 1;
    }
    return 0;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        ST();
        int l=0,r=n-1,len;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))len=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d %dn",res,len);
        for(int i=0;i<res;i++)printf("%d%c",ans[i],i==res-1?'n':' ');
    }
    return 0;
}