题解 CF1063F 【String Journey】

xtx1092515503 · 2020-08-07 14:43:53 · 题解

CF1063F String Journey

这里是一种奇怪的SA+笛卡尔树+线段树的解法。

首先，我们发现，对于一条 \text{Journey}，我们一定可以把它掐头去尾，做到 \text{Journey} 中第 i 个字符串的长度是 k-i+1。这很显然，因为要保证后一个串是前一个串的真子串，只需要保证前一个串的长度比后一个长 1 即可。

于是我们可以很自然的想到DP。设 f_i 表示以 i 开头的那条后缀，以它开始的 \text{Journey} 最多能有多长。显然这个DP顺序应该是从后往前DP的。

则 f_j 能转移到 f_i，当且仅当 i<j-f_j，并且 \operatorname{LCP}(suf_i,suf_j)\geq f_j 或 \operatorname{LCP}(suf_{i+1},suf_j)\geq f_j 二者中有至少一条成立。i<j-f_j 是为了保证 \text{Journey} 中任意两个串都不会重叠。

考虑到 (suf_i,suf_j)\geq f_j 成立的位置，实际上是后缀数组中的一段区间，所以我们只需要在后缀数组中二分出来成立的区间，然后用线段树进行区间取 \max 即可。

但是这个算法有一个地方假掉了，感兴趣的可以看看这份记录。而我们接下来要讲解它到底是怎么假掉的以及如何让它不假。

在经过无数对拍后，我们会发现一件惨痛的事实：能转移的不仅仅是 f_j，所有的 k\in[1,f_j]，全部都能转移到 i 来。我们不得不枚举所有这样的 k 进行转移。因为 f_i 最大只会到 O(\sqrt{n}) 的级别，这种做法是 O(n\sqrt{n}\log n)的，所以最终T了。感兴趣的可以看看这份记录。

那这种方法如何优化呢？

如果刷题够多，或者打了很多表的话，应该可以敏锐地发现，我们在后缀数组中二分出来的区间，虽然一共要枚举 O(n\sqrt{n}) 次区间，但是实际上这 n\sqrt{n} 个区间中只有 n 个不同的。更准确地说，这就是你在 ht 数组上建出笛卡尔树后，笛卡尔树上每个节点所代表的区间。

（这里的笛卡尔树的形态可能比较奇怪，详细的介绍可以参照另一道题的题解）

于是我们可以建出笛卡尔树出来。然后，假设我们要更新所有的 k\in[1,f_j]，我们可以先通过树上倍增找到 j 节点的祖先中深度最小的使得 ht_x\geq f_j 成立的节点 x。则 j 可以更新到的区间，便是 x 以及它的所有祖先节点所代表的区间。

我们初始令 k=ht_j，表示当前节点所对应的更新值。接着，我们不断往上跳父亲进行更新。

我们可以为每个节点设一个 mx_x，表示所有来更新过 x 的 k 中，最大的那个 k 是什么。假如到了一个节点后，发现已有 k\leq mx_x，便可以直接退出了，因为所有 x 的祖先都已经被产生 mx_x 的那一次更新给直接更新到头了。

否则，先将 k 与 ht_x 取 \min（因为只有 k\leq ht_x，k才有可能更新到 x所代表的整个区间），然后用 k 来与 mx_k 进行取 \max，然后继续更新。

它用代码实现下来，就是这样的：

void func(int u){
    int x=pos[rk[u]];
    for(int i=19;i>=0;i--)if(ht[anc[x][i]]>=f[u])x=anc[x][i];
    int y=f[u];
    while(x){
        y=min(y,ht[x]);
        if(mx[x]>=y)break;
        mx[x]=y;
        if(u-y-1>=0)v[u-y-1].push_back(make_pair(x,y));
        x=anc[x][0];
    }
}

稍微说明一下。代码中的 u 对应着讲解中的 j，而 y 对应着讲解中的 k。pos[rk[u]] 是 u 在笛卡尔树中对应的节点。然后那一句 push_back，表示我们在 u-y-1 的位置储存一次更新，因为我们初始的转移式有 i<j-f_j 一句限制，所以必须这样处理。

我们来分析一下复杂度。很明显，这样写出来后，每一次更新，除了树上倍增出来的那个节点（即一开始的 x）以后还有可能再被更新以外，其它祖先节点都不可能再被更新了（都已经被更新到头了）。则更新的总次数应是 O(n) 级别的。每次更新都是 O(\log n) 的（需要使用线段树），因此更新的复杂度便是 O(n\log n) 的。另外还有 O(n\log n) 的树上倍增和预处理倍增数组，O(n)的笛卡尔树建树，以及 O(n\log n)的后缀排序。因此综合下来，总复杂度便是 O(n\log n) 的，实际跑起来也很快，因为树上倍增和线段树的 \log n 都是常数很小的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500100;
int f[N],res;
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,mn[N][20],LG[N];
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
    }
}
using namespace Suffix_Array;
//-------------------SegMentTree Below-----------------
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define pushdown(x) tag[lson]=max(tag[lson],tag[x]),tag[rson]=max(tag[rson],tag[x]),tag[x]=0
int tag[N<<2];
void modify(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){tag[x]=max(tag[x],val);return;}
    pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val);
}
int query(int x,int l,int r,int P){
    if(l==r)return tag[x];
    pushdown(x);
    return P<=mid?query(lson,l,mid,P):query(rson,mid+1,r,P); 
}
vector<pair<int,int> >v[N];
#undef lson
#undef rson
#undef mid
int L[N],R[N],lson[N],rson[N],anc[N][20],stk[N],tp,pos[N],mx[N];
void dfs(int x,int fa){
    anc[x][0]=fa;
    if(lson[x])dfs(lson[x],x);
    else pos[L[x]]=x;
    if(rson[x])dfs(rson[x],x);
    else pos[R[x]-1]=x;
}
void func(int u){
    int x=pos[rk[u]];
//  printf("FUNC:%d:%d\n",x,f[u]);
    for(int i=19;i>=0;i--)if(ht[anc[x][i]]>=f[u])x=anc[x][i];
    int y=f[u];
    while(x){
        y=min(y,ht[x]);
        if(mx[x]>=y)break;
//      printf("%d,%d\n",x,y);
        mx[x]=y;
        if(u-y-1>=0)v[u-y-1].push_back(make_pair(x,y));
        x=anc[x][0];
    }
}
int main(){
    scanf("%d%s",&n,s),m='z';
    SA();
//  for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");

    for(int i=1;i<n;i++){
        while(tp&&ht[stk[tp]]>ht[i])lson[i]=stk[tp],R[stk[tp]]=i,tp--;
        if(tp)rson[stk[tp]]=i;
        L[i]=stk[tp];
        stk[++tp]=i;
    }
    while(tp)R[stk[tp--]]=n;

    dfs(stk[1],0);
    for(int j=1;j<=19;j++)for(int i=1;i<n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];
    for(int i=n-1;i>=0;i--){
        for(auto j:v[i])modify(1,0,n-1,L[j.first],R[j.first]-1,j.second);
        f[i]=query(1,0,n-1,rk[i]);
        if(i+1<n)f[i]=max(f[i],query(1,0,n-1,rk[i+1]));
        f[i]++;
        res=max(res,f[i]);
        func(i);
    }
    printf("%d\n",res);
    return 0;
}