CF700E Cool Slogans

Description

给定长度为 $n$ 的字符串 s ，要求构造字符串序列 $s_1,s_2,\cdots,s_k$ ，满足 $\forall i\in[1,k]$ ，$s_i$ 是 s 的子串，且 $\forall i\in[2,k]$， 都有 $s_{i-1}$ 在 $s_i$ 中至少出现了两次（可以有重叠部分）。$s_i$ 不能为空。求最大的 $k$ 值。
$1\leq n\leq 2\times 10^5$

Solution

有的时候做题没有灵感，翻题解时会发现题解先给定了几条十分显然的结论，然后思路就打开了。结论虽然显然，但问题就在于自己想不到，或者说，不明白自己为什么要往那方面想😓。

比如这道题。有一个很好证明的结论就是：

存在至少一种方案，满足 $\forall i\in[1,k-1]$，$s_i$ 是 $s_{i+1}$ 的后缀。

证明可以这样考虑：如果 $s_{i+1}$ 后面还多了一段，删去这段使得 $s_i$ 成为后缀后对于序列并无影响。

于是最终的序列一定是 parent 树上的一条链上选若干个。似乎可以用树形 dp 来处理。设 f[u] 表示第 $i$ 个节点及其祖先可以构成的最长序列的长度。
考虑转移的条件。对于 $u$ 及其祖先节点 $v$ ，若 $v$ 在某个 $u 代表的字符串中出现两次则执行 f[u]=f[v]+1 ，否则执行 f[u]=f[v] 。问题转化为了如何判定 $v$ 在某个 $u$ 代表的字符串中的出现次数。
节点 $u$ 有不止一个 endpos 难道需要一一枚举再分别判定吗？我们先钦定判定 $u$ 的第一个 endpos 位置 $p$ ， 那么我们需要在 $[p-a[u].l+a[v].l,p]$ 范围内查询 $v$ 的 endpos 数目，这个范围是属于 $[p-a[u].l+1,p]$ 的，即对于每个结束节点 $p$ ，$s[p-a[u].l+a[v].l,p]$ 这个字符串都必然是一样的，于是我们只要任意判定一个就行了。
至此我们得到了一个 $\mathcal{O}(n^2\log_2{n})$ 的 dp ：枚举 parent 树上的点 $u$ 及其祖先节点 $v$ 并尝试更新。

但是我们有必要枚举每个祖先吗？如果 $u$ 不能由其父节点 $v$ 转移过来，那么用 $v$ 去更新 $u$ 的子节点肯定不会更劣。我们可以把 $u$ 给压缩到 $v$ 中去。
复杂度成功优化到 $\mathcal{O}(n\log_2{n})$ 。

const int N=4e5+5;
using namespace std;
namespace SEG{
#define mid (l+r>>1)
#define Ls c[p][0],l,mid
#define Rs c[p][1],mid+1,r
    int tot;
    int t[N<<5],c[N<<5][2];
    void modify(int &p,int l,int r,int pos){
        p=++tot;t[p]=1;
        if(l==r) return;
        if(pos<=mid) modify(Ls,pos);
        else modify(Rs,pos);
    }
    void merge(int &p,int x,int l,int r){
        if(!p||!x) return p=p|x,void();
        int now=++tot;
        c[now][0]=c[p][0],c[now][1]=c[p][1];t[now]=t[p]+t[x];p=now;
        if(l==r) return;
        merge(c[p][0],c[x][0],l,mid);
        merge(c[p][1],c[x][1],mid+1,r);
    }
    int query(int p,int l,int r,int nl,int nr){
        if(!p) return 0;
        if(l>=nl&&r<=nr) return t[p];
        int ret=0;
        if(mid>=nl) ret+=query(Ls,nl,nr);
        if(mid< nr) ret+=query(Rs,nl,nr);
        return ret;
    }
}
using namespace SEG;
namespace SAM{
    int tot,las;
    int f[N],g[N],ba[N],rk[N],rt[N],pos[N];
    struct node{
        int l,link,c[26];
    }a[N];
    void insert(int k,int id){
        int p=las,cur=las=++tot;
        a[cur].l=a[p].l+1;pos[cur]=id;
        while(p&&!a[p].c[k]) a[p].c[k]=cur,p=a[p].link;
        if(!p) return a[cur].link=1,void();
        int q=a[p].c[k];
        if(a[q].l==a[p].l+1) return a[cur].link=q,void();
        int now=++tot;a[now]=a[q];a[now].l=a[p].l+1;
        a[q].link=a[cur].link=now;pos[now]=pos[q];
        while(p&&a[p].c[k]==q) a[p].c[k]=now,p=a[p].link;
    }
    void basesort(){
        for(int i=1;i<=tot;++i) ++ba[a[i].l];
        for(int i=1;i<=tot;++i) ba[i]+=ba[i-1];
        for(int i=1;i<=tot;++i) rk[ba[a[i].l]--]=i;
    }
    void build(char *s){
        tot=las=1;
        int len=strlen(s+1);
        for(int i=1;i<=len;++i)
            insert(s[i]-='a',i);
        for(int i=1,u=1;i<=len;++i)
            u=a[u].c[int(s[i])],modify(rt[u],1,len,i);
        basesort();
        for(int i=tot,u=rk[i];i>=2;--i,u=rk[i])
            merge(rt[a[u].link],rt[u],1,len);
        int ans=1;f[1]=1;g[1]=1;
        for(int i=2,u=rk[i];i<=tot;++i,u=rk[i]){
            int fa=a[u].link;
            if(fa==1){
                f[u]=1,g[u]=u;continue;
            }
            if(query(rt[g[fa]],1,len,pos[u]-a[u].l+a[g[fa]].l,pos[u]-1))
                f[u]=f[fa]+1,g[u]=u;
            else f[u]=f[fa],g[u]=g[fa];
            ans=max(ans,f[u]);
        }
        printf("%d\n",ans);
    }
}