[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)

发布于 2018-03-25  67 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查,他发现:虽然他不能预见明天产奶的质量,但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时,这个长度为4。

Tag

后缀数组,单调队列

题目大意

求出现次数大于K的最长子串

解决思路

后缀数组求出Height后,问题转化为求数列中连续长度为K的连续数列中最小值的最大值,这个可以用单调队列维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=50010;
const int maxNum=2000100;
const int inf=2147483647;

int n,K;
int Arr[maxN];
int SA[maxN],Rank[maxN],Height[maxN];
int Cnt[maxNum],CntA[maxN],CntB[maxN],A[maxN],B[maxN],SSA[maxN];
int Queue[maxN];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>K;
    for (int i=1;i<=n;i++) cin>>Arr[i];
    //GetSA
    for (int i=1;i<=n;i++) Cnt[Arr[i]]++;
    for (int i=1;i<maxNum;i++) Cnt[i]+=Cnt[i-1];
    for (int i=n;i>=1;i--) SA[Cnt[Arr[i]]--]=i;
    Rank[SA[1]]=1;
    for (int i=2;i<=n;i++)
    {
        Rank[SA[i]]=Rank[SA[i-1]];
        if (Arr[SA[i]]!=Arr[SA[i-1]]) Rank[SA[i]]++;
    }
    for (int l=1;Rank[SA[n]]!=n;l=l<<1)
    {
        mem(CntA,0);mem(CntB,0);
        for (int i=1;i<=n;i++)
        {
            CntA[A[i]=Rank[i]]++;
            CntB[B[i]=((i+l<=n)?(Rank[i+l]):(0))]++;
        }
        for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1],CntB[i]+=CntB[i-1];
        for (int i=n;i>=1;i--) SSA[CntB[B[i]]--]=i;
        for (int i=n;i>=1;i--) SA[CntA[A[SSA[i]]]--]=SSA[i];
        Rank[SA[1]]=1;
        for (int i=2;i<=n;i++)
        {
            Rank[SA[i]]=Rank[SA[i-1]];
            if ((A[SA[i]]!=A[SA[i-1]])||(B[SA[i]]!=B[SA[i-1]])) Rank[SA[i]]++;
        }
    }
    for (int i=1,j=0;i<=n;i++)
    {
        if (j) j--;
        while (Arr[i+j]==Arr[SA[Rank[i]-1]+j]) j++;
        Height[Rank[i]]=j;
    }
    int Ans=0,l=0,r=0;
    K--;
    //单调队列维护长度为K的序列的最小值,每次取出队首即为当前的最小值,对这些最小值取最大值
    for (int i=1;i<=n;i++)
    {
        while ((l<r)&&(Height[i]<Height[Queue[r]])) r--;
        Queue[++r]=i;
        if (i<K) continue;//注意当i的长度小于K的时候,不应该加入答案
        while ((l<r)&&(i-K+1>Queue[l])) l++;
        Ans=max(Ans,Height[Queue[l]]);
    }
    cout<<Ans<<endl;
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)


HNCJ OIer