题解 P4482 【[BJWC2018]Border 的四种求法】

· · 题解

Q $ 次询问子串的最长 Border. $ |S|,Q\le 2\times 10^5

求 [l,r] 的 border 等价于选一个最大的 i\in [l,r) ,使 \text{LCS}([1,i],[1,r])\ge i-l+1 。比较难以处理的是，这个条件没有单调性。

考虑前缀的 \text{LCS} 在前缀树（也是 SAM 的 parent 树）上就是 LCA 表示的状态的长度。那么一种naive的做法就是先线段树合并处理 endpos 集合，然后枚举前缀树上的每个祖先 u ，在 u 的 endpos 集合中找一个在 [l,\min(r-1,l+len(u)-1)] 中且最大的位置。
理论最坏是平方。但是能过

常用套路树上倍增在这里也没法用，因为从下到上 endpos 集合增大，但 len 值减小，同样不单调。

将问题转化一步，记表示 [1,r] 的节点为 u .等价于从整个前缀树中选一个前缀节点 v (记其表示 [1,i] )，要求 len(\text{LCA}(u,v))\ge i-l+1 (\ i-len(\text{LCA}(u,v))<l)且 i 尽量大。

用链分治来搞这件事。考虑先划分轻重链，一个点到根的路径划分为至多 \log_2 n 段（且每一段都是一条重链的子段）。

对于每一段，记其中最深的点（就是进去那个点）为 S ,链顶端为 top .则贡献为：

容易发现，各条重链的贡献可能有重叠的部分，但一定没有遗漏，具体处理如下：
对于第一种情况，我们同样用线段树合并。每个询问的代价是 \mathcal O(\log^2 n) .
所有重链长度之和为 \mathcal O(n) ,所有轻子树大小之和是 \mathcal O(n\log n) ,所以后两种贡献总共涉及 \mathcal O(n\log n) 个点，这很好（因此我们的链分治才是有意义的，并且第一种情况必须用线段树合并做，否则这里的点数就爆炸了）。
维护一棵线段树，第 i 个叶子存 i-len(LCA(u,S)) 的值（u是表示 [1,i] 的点）。将“重链上 S 上面的点及其轻子树”中的前缀点全部在线段树上修改。对于 S 上的每个询问，在线段树上找一个最大的 i 满足 i<r,i-len(LCA(u,S))<l 。这可以用线段树上二分做到。

将询问离线，放到每个段最深的点（进去的点）上，统一处理所有询问即可。

总时间复杂度 \mathcal O((n+Q)\log^2 n) ，空间复杂度 \mathcal O((n+Q)\log n)

一些细节：处理完一条重链后要撤销其在线段树上的修改。

另外，似乎网上的好几份代码都在我造的几组|S|=10,Q=50,字符集为\{a,b\}的数据下挂掉了。好像是他们的线段树上二分写的不太对（比如区间为空时）

const int INF=1e9;
#define MAXN 400011
int n,root[MAXN],cnt=0;
struct Endp
{
    struct node{int lson,rson;}t[MAXN<<6|1];
    #define rt t[num]
    void insert(int& num,un pos,un l=1,un r=n)
    {
        if(!num)num=++cnt;
        if(l==r)return;
        un mid=(l+r)>>1;
        if(pos<=mid)insert(rt.lson,pos,l,mid);
        else insert(rt.rson,pos,mid+1,r);
    }
    int Query(int num,int upp,un l=1,un r=n)
    {
        if(!num||upp<1)return 0;
        if(l==r)return l;
        un mid=(l+r)>>1;
        int res=0;
        if(upp>mid)res=Query(rt.rson,upp,mid+1,r);
        if(res)return res;
        return Query(rt.lson,upp,l,mid);
    }
    int merge(int x,int y,un l=1,un r=n)
    {
        if(!x||!y)return x|y;
        if(l==r)return x;
        int num=++cnt;un mid=(l+r)>>1;
        rt.lson=merge(t[x].lson,t[y].lson,l,mid);
        rt.rson=merge(t[x].rson,t[y].rson,mid+1,r);
        return num;
    }
    void debug(un l,un r,un num)
    {
        if(l==r){printf("%d ",l);return;}
        un mid=(l+r)>>1;
        if(rt.lson)debug(l,mid,rt.lson);
        if(rt.rson)debug(mid+1,r,rt.rson);
    }
}endp;

struct Segment_Tree
{
    int t[MAXN<<2|1];
    void build(un l=1,un r=n,un num=1)
    {
        rt=INF;
        if(l==r)return;
        else build(l,(l+r)>>1,num<<1),build(((l+r)>>1)+1,r,num<<1|1);
    }
    void modify(un pos,int val,un l=1,un r=n,un num=1)
    {
        if(l==r){rt=val;return;}
        un mid=(l+r)>>1;
        if(pos<=mid)modify(pos,val,l,mid,num<<1);
        else modify(pos,val,mid+1,r,num<<1|1);
        rt=min(t[num<<1],t[num<<1|1]);
    }
    int Query(int upp,int lim,un l=1,un r=n,un num=1)
    {
        if(rt>=lim)return 0;
        if(l==r)return rt<lim?l:0;
        un mid=(l+r)>>1;
        int res=0;
        if(upp>mid)res=Query(upp,lim,mid+1,r,num<<1|1);
        if(res)return res;
        return Query(upp,lim,l,mid,num<<1);
    }

}sgt;
struct SAM
{

    int t[MAXN][26],pre[MAXN],len[MAXN],End[MAXN];
    int last,tot;
    SAM(){last=tot=1;}
#define from(u) for(int i=head[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
    void extend(int w,int dex)
    {
        int pos=last,cur=++tot;
        len[cur]=len[pos]+1,last=cur,End[cur]=dex;
        while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
        if(!pos){pre[cur]=1;return;}
        int nxt=t[pos][w];
        if(len[nxt]==len[pos]+1)pre[cur]=nxt;
        else
        {
            int tmp=++tot;
            len[tmp]=len[pos]+1,memcpy(t[tmp],t[nxt],sizeof t[nxt]);
            pre[tmp]=pre[nxt],pre[cur]=pre[nxt]=tmp;
            while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
        }
    }

    struct one{int l,r,dex;};
    std::vector<one>q[MAXN];
    int ans[MAXN];
    struct edge{int v,nxt;}e[MAXN<<1|1];
    int cnt,head[MAXN];
    void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;}
    int size[MAXN],dep[MAXN],mson[MAXN],top[MAXN];
    void dfs1(int u)
    {
        size[u]=1;
        if(End[u])endp.insert(root[u],End[u]);
        from(u)
        {
            dep[v]=dep[u]+1,dfs1(v);
            size[u]+=size[v];
            if(size[v]>size[mson[u]])mson[u]=v;
            root[u]=endp.merge(root[u],root[v]);
        }
    }
    void dfs2(int u,int now_top)
    {
        top[u]=now_top;
        if(mson[u])dfs2(mson[u],now_top);
        from(u)
            if(v!=mson[u])dfs2(v,v);
    }
    void build()
    {
        for(int i=2;i<=tot;++i)adde(pre[i],i);
        dfs1(1),dfs2(1,1);
    }

    void push(int u,int k)
    {
        if(End[u])sgt.modify(End[u],End[u]-k);
        from(u)push(v,k);
    }
    void back(int u)
    {
        if(End[u])sgt.modify(End[u],INF);
        from(u)back(v);
    }
    void solve(int S)
    {
        for(int u=S;u;u=mson[u])
        {
            if(End[u])sgt.modify(End[u],End[u]-len[u]);
            from(u)
                if(v!=mson[u])push(v,len[u]);
            // printf("consider %d,len=%d\n",u,len[u]);
            for(auto x:q[u])
            {
                int res=endp.Query(root[u],min(x.r-1,x.l+len[u]-1));
                if(res>=x.l)umax(ans[x.dex],res-x.l+1);
                res=sgt.Query(x.r-1,x.l);
                if(res>=x.l)umax(ans[x.dex],res-x.l+1);
            }
        }
        for(int u=S;u;u=mson[u])
        {
            if(End[u])sgt.modify(End[u],INF);
            from(u)
                if(v!=mson[u])back(v);
        }
        for(int u=S;u;u=mson[u])
            from(u)
                if(v!=mson[u])solve(v);
    }
}sam;
int ed[MAXN];
char s[MAXN];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i)sam.extend(s[i]-'a',i),ed[i]=sam.last;
    sam.build();
    // endp.debug(1,n,root[ed[2]]);
    // puts("?");
    // printf("Res=%d\n",endp.Query(root[1],1));
    int query=read();
    for(int i=1;i<=query;++i)
    {
        int l=read(),r=read();
        if(l==r){sam.ans[i]=0;continue;}
        int pos=ed[r];
        while(pos)sam.q[pos].push_back({l,r,i}),pos=sam.pre[sam.top[pos]];
    }
    sgt.build();
    sam.solve(1);
    for(int i=1;i<=query;++i)printf("%d\n",sam.ans[i]);
    return 0;
}