专栏文章

题解：P14021 [ICPC 2024 Nanjing R] Border 之跃 2

山山田リョウ
P14021题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minxwkt2
此快照首次捕获于
2025/12/02 10:09
3 个月前
此快照最后确认于
2025/12/02 10:09
3 个月前
查看原文
提供一个 1log 做法。
容易想到一个暴力的做法：枚举 l≤x≤y≤rl\leq x\leq y\leq r，求 s[1,y]s[1,y] 和 rev(s[x,n])\text{rev}(s[x,n]) 最长的长度小于 y−x+1y-x+1 的公共后缀，转移跳进去的情况。
对于长度的限制有点唐，但是容易发现倘若有公共后缀不小于 y−x+1y-x+1 了则说明 s[x,y]s[x,y] 是回文串。
对于一个长度为 aa、回文中心极长同色段长度为 bb 的回文串，其答案应为 a−b2+b−1\frac{a-b}{2}+b-1，这个贪心策略的证明是简单的。
那我们不妨把回文串单独做（查询区间内最大权值回文串只需要二维数点即可，分讨一下是否触碰到边即可），那对于剩下部分，我们要解决的事情是：枚举 l≤x≤y≤rl\leq x\leq y\leq r，求 s[1,y]s[1,y] 和 rev(s[x,n])\text{rev}(s[x,n]) 的 LCS，如果其长度不小于 y−x+1y-x+1 则跳过，否则转移跳进去的情况。
于是发现我们下一步跳进的字符串一定是回文串或某个前缀和某个反串前缀的 LCS，对所有前缀和反串前缀建 Trie 树，那么 LCS 即为 Trie 树上 LCA，显然只需要对这些前缀和反串前缀对应点建虚树就好了，这个东西对应的也显然就是对正反串建广义后缀自动机（你只需要写个 SA 然后按照 height 数组建多叉笛卡尔树即可）。于是这样你跳一步后的有效位置就只有 O(n)O(n) 个了。
所以我们考虑把这 O(n)O(n) 个子串的答案求出来，显然一个 Endpos 集合最大元的最长真前缀也是 Endpos 集合最大元，那你可以从它转移，于是剩下的情况只有跳进去的串反着出现位置是 s[l,r]s[l,r] 的后缀。
根据前面的讨论，你特判掉回文串剩下的东西就是左端点在 [l,r−k][l,r-k] 中的后缀的反串（kk 是 s[l,r]s[l,r] 上最长回文后缀）对应结点与 s[1,r]s[1,r] 对应的结点深度最深的 LCA（不妨称前者对应的集合为 VV，后者为 uu），根据虚树的结论应为 uu 与 VV 中结点关于 uu 在 dfn 序上的前驱后继结点的 LCA 较深者。
于是这样你就在 O(nlog⁡n)O(n\log n) 的时间复杂度内处理出了这些特殊点的答案。
全串显然是特殊点，于是你可以直接输出就通过了。
CPP
#include<bits/stdc++.h>
using namespace std;
namespace AfterTheRainStops{//雨停酱可爱捏~ 最喜欢雨停姐姐了！！！
namespace sam{
int trans[4000000][26];
int fail[4000000],len[4000000],pre[4000000],nodetot;
void init(){nodetot=0,fail[0]=-1,len[0]=0,memset(trans[0],0,sizeof(trans[0]));}
int append(int p,char c){
    c-='a';
    int cur=++nodetot;
    for(len[cur]=len[p]+1,pre[cur]=p,memset(trans[cur],0,sizeof(trans[cur]));(~p)&&!trans[p][c];p=fail[p])trans[p][c]=cur;
    if(~p){
        int q=trans[p][c];
        if(len[p]+1<len[q]){
            int clone=++nodetot;
            for(fail[clone]=fail[q],len[clone]=len[p]+1,pre[clone]=p,memcpy(trans[clone],trans[q],sizeof(trans[clone])),fail[cur]=fail[q]=clone;(~p)&&trans[p][c]==q;p=fail[p])trans[p][c]=clone;
        }else fail[cur]=q;
    }else fail[cur]=0;
    return cur;
}
}
int n;
char s[1000001];
namespace pam{
map<char,int>trans[1000002];
int fail[1000002],len[1000002],pos[1000002],lst,tot;
void init(){len[0]=-1,lst=1,tot=2;trans[0].clear(),trans[1].clear();}
int getfail(int x,int i){
    for(;i-len[x]<1||s[i-len[x]-1]!=s[i];x=fail[x]);
    return x;
}
void insert(int i){
    int x=getfail(lst,i);
    if(!trans[x].count(s[i])){
        len[tot]=len[x]+2;
        int y=getfail(fail[x],i);
        fail[tot]=trans[y].count(s[i])?trans[y][s[i]]:1;
        trans[x][s[i]]=tot;
        trans[tot++].clear();
    }
    pos[i]=lst=trans[x][s[i]];
}
}
int pos[4000000],a[1000000];
int build_sam(){
    int p=0,lst=0,lst1,lst2;sam::init();
    for(;p<n&&s[p]==s[n-p-1];++p)pos[a[n-p-1]=lst=sam::append(lst,s[p])]=p;
    for(lst1=lst,lst2=lst;p<n;++p)pos[lst1=sam::append(lst1,s[p])]=p,a[n-p-1]=lst2=sam::append(lst2,s[n-p-1]);
    return lst1;
}
void build_pam(){
    pam::init();
    for(int i=0;i<n;++i)pam::insert(i);
}
int f[4000000],g[1000002],p[4000000];
char type[1000002];
vector<int>ch1[4000000],ch2[1000002];
int dfn1[4000000],dfa1[4000000],dfn2[1000002],dfa2[1000002],dfntot;
int son1[4000000],tp1[4000000];
int son2[1000002],tp2[1000002];
int dfs1(int u){
    dfa1[dfn1[u]=dfntot++]=u;
    int s=1,mxs=0,t;son1[u]=0;
    for(const auto&v:ch1[u]){
        s+=(t=dfs1(v));
        if(t>mxs)son1[u]=v,mxs=t;
    }return s;
}
int lca(int u,int v){
    for(;tp1[u]!=tp1[v];)
        if(dfn1[tp1[u]]<dfn1[tp1[v]])v=sam::fail[tp1[v]];
        else u=sam::fail[tp1[u]];
    return dfn1[u]<dfn1[v]?u:v;
}
int dfs2(int u){
    int s=1,mxs=0,t;son2[u]=0;
    for(const auto&v:ch2[u]){
        s+=(t=dfs2(v));
        if(t>mxs)son2[u]=v,mxs=t;
    }return s;
}
void dfs3(int u){
    dfa2[dfn2[u]=dfntot++]=u;
    if(son2[u])tp2[son2[u]]=tp2[u],dfs3(son2[u]);
    for(const auto&v:ch2[u])
        if(v!=son2[u])
            tp2[v]=v,dfs3(v);
}
int fail[4000000];
int ql[4000000],qr[4000000],pr[4000000],sf[4000000];
vector<int>buc[1000000];
int tr[8388608];
void work(){
    scanf(" %s",s),n=strlen(s);
    int wytqwq=build_sam();build_pam();
    for(const auto&[c,u]:pam::trans[0])type[u]=c,g[u]=0;
    for(const auto&[c,u]:pam::trans[1])type[u]=c,g[u]=1;
    for(int i=2;i<pam::tot;++i)
        for(const auto&[c,u]:pam::trans[i]){
            if(c==type[i])type[u]=c,g[u]=g[i]+2;
            else type[u]=0,g[u]=g[i]+1;
        }
    for(int i=0;i<=sam::nodetot;++i)ch1[i].clear();
    for(int i=1;i<=sam::nodetot;++i)ch1[sam::fail[i]].push_back(i);
    dfntot=0,dfs1(0);
    for(int i=1;i<=sam::nodetot;++i)p[i]=i;
    std::sort(p+1,p+sam::nodetot+1,[](const auto&x,const auto&y){return sam::len[x]<sam::len[y];});
    for(int i=1,u;i<=sam::nodetot;++i)u=p[i],tp1[u]=son1[sam::fail[u]]==u?tp1[sam::fail[u]]:u;
    for(int i=sam::nodetot,u;i;--i)if(~pos[u=p[i]])pos[sam::fail[u]]=pos[u];
    for(int i=1;i<pam::tot;++i)ch2[i].clear();
    for(int i=2;i<pam::tot;++i)ch2[pam::fail[i]].push_back(i);
    dfs2(1),dfntot=0,dfs3(1);
    for(int i=0;i<n;++i)buc[i].clear();
    for(int i=1,u;i<=sam::nodetot;++i){
        u=p[i];
        if(pos[u]<0)continue;
        fail[u]=pam::pos[pos[u]];
        for(;pam::len[tp2[fail[u]]]>sam::len[u];fail[u]=pam::fail[tp2[fail[u]]]);
        int l=dfn2[tp2[fail[u]]],r=dfn2[fail[u]];
        for(;l<r;){
            int mid=l+r+1>>1;
            if(pam::len[dfa2[mid]]>sam::len[u])r=mid-1;
            else l=mid;
        }fail[u]=dfa2[l];
        if(pam::len[fail[u]]<sam::len[u])ql[u]=pos[u]-sam::len[u]+1,buc[qr[u]=pos[u]-pam::len[fail[u]]].push_back(u);
    }
    int sz=1;
    for(;sz<=sam::nodetot;sz<<=1);
    for(int i=1;i<(sz<<1);++i)tr[i]=-1;
    for(int i=0;i<n;++i){
        for(int cur=dfn1[a[i]]+sz;cur;cur>>=1)tr[cur]=i;
        for(const auto&u:buc[i]){
            int cur=dfn1[u]+sz;
            if(tr[cur]>=ql[u])pr[u]=sf[u]=u;
            else{
                for(;cur;cur>>=1)
                    if((cur&1)&&tr[cur^1]>=ql[u]){
                        cur^=1;break;
                    }
                if(!cur)pr[u]=-1;
                else{
                    for(;cur<sz;cur=cur<<1|(tr[cur<<1|1]>=ql[u]));
                    pr[u]=dfa1[cur-sz];
                }
                cur=dfn1[u]+sz;
                for(;cur;cur>>=1)
                    if(!(cur&1)&&tr[cur^1]>=ql[u]){
                        cur^=1;break;
                    }
                if(!cur)sf[u]=-1;
                else{
                    for(;cur<sz;cur=cur<<1|(tr[cur<<1]<ql[u]));
                    sf[u]=dfa1[cur-sz];
                }
            }
        }
    }
    f[0]=-1;
    for(int i=1,u;i<=sam::nodetot;++i){
        u=p[i];
        if(pos[u]<0)continue;
        if(pam::len[fail[u]]<sam::len[u]){
            f[u]=max(max(f[sam::pre[u]],f[sam::fail[u]]),g[fail[u]]);
            if(~pr[u])f[u]=max(f[u],f[lca(pr[u],u)]+1);
            if(~sf[u])f[u]=max(f[u],f[lca(sf[u],u)]+1);
        }else f[u]=g[fail[u]];
        pos[u]=-1;
    }printf("%d\n",f[wytqwq]);
}
void main(){
    memset(pos,-1,sizeof(pos));
    int t;
    for(scanf("%d",&t);t--;work());
}
}
int main(){
    AfterTheRainStops::main();
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...