P5561 题解

· · 题解

每个子串出现的时间都是一段区间，考虑线段树分治。

线段树的每个节点动态维护当前 \text{LCP} 对应的子串，每次加入新串时更新。

那么瓶颈变为求任意两个子串的 \text{LCP}。

先把所有串接在一起建反串 SAM。

一个观察是任意子串 \text{LCP} 可以看作两端后缀的 \text{LCP} 对子串长度取 \min。因此，预处理出每段后缀在反串 SAM 上的位置，然后用 O(n\log n)-O(1) LCA 即可做到 O(n\log n) 的总复杂度。

但是本题过于卡空间，要把欧拉序求 LCA 换成树剖求 LCA。虽然变成了 O(n\log ^2 n) 但其实比原先快了三分之一。

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int maxn=2000010;
const int MAXN=4000010;
il int read(){
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
struct edge{
    int v,to;
}e[maxn<<1];
int head[maxn],ecnt;
void addedge(int u,int v){
    e[++ecnt].v=v,e[ecnt].to=head[u],head[u]=ecnt;
}
struct sam{
    int ch[26],fa,len;
}a[maxn];
int loc[maxn],cnt=1,End=1;
void Insert(int c){
    int t=End,x=End=++cnt,nt=0,nx; a[x].len=a[t].len+1;
    loc[a[x].len]=x;//////////////////
    for(;t&&!nt;t=a[t].fa,nt=a[t].ch[c]) a[t].ch[c]=x;
    if(!t){a[x].fa=1;return ;}
    if(a[t].len+1==a[nt].len){a[x].fa=nt;return ;}
    nx=++cnt,a[nx].len=a[t].len+1;
    a[nx].fa=a[nt].fa,a[nt].fa=a[x].fa=nx;
    for(int i=0;i<26;i++) a[nx].ch[i]=a[nt].ch[i];
    for(;a[t].ch[c]==nt;t=a[t].fa) a[t].ch[c]=nx;
}
struct str{
    int l,r,tl,tr;
}A[maxn];
int sz[maxn],zson[maxn],dep[maxn],fa[maxn];
int dfn[maxn],DFN[maxn],top[maxn],idx;
void dfs1(int fath,int x){
//  printf("!!!%d\n",x);
    dep[x]=dep[fath]+1,fa[x]=fath;
    for(int i=head[x];i;i=e[i].to)
        if(e[i].v^fath){
            dfs1(x,e[i].v),sz[x]+=sz[e[i].v];
            if(sz[zson[x]]<sz[e[i].v]) zson[x]=e[i].v;
        }sz[x]++; 
}
void dfs2(int x){
    dfn[x]=++idx,DFN[idx]=x;
    if(zson[fa[x]]^x) top[x]=x;
    else top[x]=top[fa[x]];
    if(zson[x]) dfs2(zson[x]);
    for(int i=head[x];i;i=e[i].to)
        if(e[i].v!=fa[x]&&e[i].v!=zson[x]) dfs2(e[i].v);
}
int dl[MAXN],dr[MAXN];
int n,m,q,L[maxn],R[maxn];
char c[maxn],C[maxn];
int lca(int x,int y){
    while(top[x]^top[y])
        dfn[top[x]]>dfn[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dfn[x]>dfn[y]?y:x;
}
int lcp(int i,int j){
    return a[lca(loc[n-i+1],loc[n-j+1])].len;
}
void Add(int i,int l,int r,int L,int R,int sl,int sr){
    if(l>=L&&r<=R){
        if(dl[i]&&dr[i]) dr[i]=dl[i]+min(lcp(dl[i],sl),min(dr[i]-dl[i]+1,sr-sl+1))-1;
        else dl[i]=sl,dr[i]=sr;
        return ;
    }int mid=l+r>>1;
    if(mid>=L) Add(i<<1,l,mid,L,R,sl,sr);
    if(mid<R) Add(i<<1|1,mid+1,r,L,R,sl,sr);
}
void Print(int i,int l,int r,int sl,int sr){
    if(dl[i]&&dr[i]){
        if(sl&&sr) sr=sl+min(lcp(dl[i],sl),min(dr[i]-dl[i]+1,sr-sl+1))-1;
        else sl=dl[i],sr=dr[i];
    }
    if(l==r){
        printf("%d\n",(sl&&sr)?sr-sl+1:0);
        return ;
    }int mid=l+r>>1;
    Print(i<<1,l,mid,sl,sr);
    Print(i<<1|1,mid+1,r,sl,sr);
}
int main(){
    m=read();
    for(int i=1;i<=m;i++){
        scanf("%s",C+1);
        L[i]=R[i-1]+1,R[i]=L[i]+strlen(C+1)-1;
        for(int j=L[i];j<=R[i];j++) c[j]=C[j-L[i]+1];
    }n=strlen(c+1);
    for(int i=n;i;i--) Insert(c[i]-'a');
    for(int i=2;i<=cnt;i++)
        addedge(a[i].fa,i),addedge(i,a[i].fa);
    dfs1(0,1),dfs2(1);
    q=read();
    for(int i=1;i<=q;i++){
        int op=read(),x=read();
        if(op==1){
            A[i].l=L[x]+read()-1;
            A[i].r=L[x]+read()-1;
            A[i].tl=i;
        }
        else A[x].tr=i-1;
    }
    for(int i=1;i<=q;i++)
        if(!A[i].tr) A[i].tr=q;
    for(int i=1;i<=q;i++)
        if(A[i].l) Add(1,1,q,A[i].tl,A[i].tr,A[i].l,A[i].r);
    Print(1,1,q,0,0);
    return 0;
}