题目:

CF700E Cool Slogans

题意：

给定一个字符串，要求构造字符串序列，满足任意都是的子串，且任意 ，都有在中出现了至少次（可以有重叠部分，只要起始、结尾位置不同即可）。
求可能的最大的 的值（即序列的最大可能长度）。

题解:

要求的字符串序列一定是的子串的，再,再......

设表示以开头的所有子串的最大值。

，当且仅当满足，为最大时的串的长度。

显然相同情况下肯定越小越好。

但是发现可以变小，来使也变小，来使可以转移。

突然发现，变小的一定和一个一样，使得被代替，所以我们就不需要考虑变小这种情况了。

但是变小的会对产生影响，因为一个，一个。(假设变小后会被代替)

我们已经求出了和了，但我们不知道是哪一个。我们要找出最小的满足且。

因为是单调不升的，所以满足的一定满足。

然后我们就可以在所有的中找最小值，因为的在数组中是连续的一段，用线段树维护一下区间就好了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
//#define int long long
const int N=1e6+5;
int n,m,ans,c[N],x[N],y[N],sa[N],rk[N],height[N],Log[N],mi[N*4],st[N][20];
char a[N];
struct node{
    int f,len;
    node(){f=1;len=1;}
}tree[N*4];
bool operator < (node a,node b)
{
    if(a.f!=b.f)return a.f<b.f;
    return a.len>b.len;
}
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void SA(int n,int m)
{
    int p=0;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int i=1;i;i=i*2)
    {
        p=0;
        for(int j=n-i+1;j<=n;j++)y[++p]=j;
        for(int j=1;j<=n;j++)
            if(sa[j]>i)y[++p]=sa[j]-i;
        for(int j=1;j<=m;j++)c[j]=0;
        for(int j=1;j<=n;j++)c[x[y[j]]]++;
        for(int j=1;j<=m;j++)c[j]+=c[j-1];
        for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);
        x[sa[1]]=1;
        p=2;
        for(int j=2;j<=n;j++)
            if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;
            else x[sa[j]]=p++;
        if(p>n)return;
        m=p;
    }
}
void Height(int n)
{
    int k=0;
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1;i<=n;i++)
    {
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
        height[rk[i]]=k;
    }
}
void ST(int n)
{
    memset(st,0x3f,sizeof(st));
    for(int i=1;i<=n;i++)st[i][0]=height[i];
    for(int i=1;i<=Log[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int LCP(int l,int r)
{
    if(l==r)return n;
    l++;
    int k=Log[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
void query(int x,int len,int &L,int &R)
{
    x=rk[x];
    int l=1,r=x;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(LCP(mid,x)>=len)r=mid;
        else l=mid+1;
    }
    L=r;
    l=x,r=n;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(LCP(x,mid)>=len)l=mid;
        else r=mid-1;
    }
    R=l;
}
void pushdown(int nod)
{
    tree[nod*2]=max(tree[nod*2],tree[nod]);
    tree[nod*2+1]=max(tree[nod*2+1],tree[nod]);
}
void change(int nod,int l,int r,int L,int R,node x)
{
    if(L>R||L>r||R<l)return;
    if(l==L&&r==R)
    {
        tree[nod]=max(tree[nod],x);
        return;
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)change(nod*2,l,mid,L,R,x);
    else if(L>mid)change(nod*2+1,mid+1,r,L,R,x);
    else{
        change(nod*2,l,mid,L,mid,x);
        change(nod*2+1,mid+1,r,mid+1,R,x);
    }
}
node find(int nod,int l,int r,int x)
{
    if(l==r)return tree[nod];
    pushdown(nod);
    int mid=(l+r)/2;
    if(x<=mid)return find(nod*2,l,mid,x);
    else return find(nod*2+1,mid+1,r,x);
}
void change2(int nod,int l,int r,int x)
{
    if(l==r)
    {
        mi[nod]=sa[x];
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)change2(nod*2,l,mid,x);
    else change2(nod*2+1,mid+1,r,x);
    mi[nod]=min(mi[nod*2],mi[nod*2+1]);
}
int find2(int nod,int l,int r,int L,int R)
{
    if(L>R||L>r||R<l)return 0x3f3f3f3f;
    if(l==L&&r==R)return mi[nod];
    int mid=(l+r)/2;
    if(R<=mid)return find2(nod*2,l,mid,L,R);
    else if(L>mid)return find2(nod*2+1,mid+1,r,L,R);
    else return min(find2(nod*2,l,mid,L,mid),find2(nod*2+1,mid+1,r,mid+1,R));
}
signed main()
{
    n=read();
    Log[0]=-1;
    for(int i=1;i<=n;i++)Log[i]=Log[i/2]+1;
    scanf("%s",a+1);
    SA(n,233);
    Height(n);
    ST(n);
    memset(mi,0x3f,sizeof(mi));
    for(int i=n;i;i--)
    {
        node xu=find(1,1,n,rk[i]);
//        cout<<xu.f<<" "<<xu.len<<endl;
        ans=max(ans,xu.f);
        if(xu.f!=1)
        {
            int L=0,R=0;
            query(i,xu.len,L,R);
            xu.len+=find2(1,1,n,L,R)-i;
        }
        xu.f++;
        int L=0,R=0;
        query(i,xu.len,L,R);
//        cout<<L<<" "<<R<<" "<<xu.f<<" "<<xu.len<<endl;
        change(1,1,n,L,R,xu);
        change2(1,1,n,rk[i]);
    }
    cout<<ans;
    return 0;
}