【题解】[十二省联考 2019] 字符串问题后缀数组+拓扑+可持久化线段树优化建图 Loj3049 —Qiuly

暴力连边的话，对于原图中的 $(x,y)$ ，将 $A_x\rightarrow B_y$ 给连上，然后如果 $B_i$ 是 $A_j$ 的前缀的话，将 $B_i\rightarrow A_j$ 连上。定义点 $A$ 的权值为其长度，点 $B$ 权值为 $0$ ，显然答案就是图上的最长路，当然如果出现了环意味着 $T$ 可以是无限长的。

求最长路可以拓扑然后存个权值最大值即可，如果还有入度大于 $1$ 的边说明有环。

容易发现第一部分的边是 $m$ 条，第二部分的是 $n_a\times n_b$ 级别的，现在考虑如何优化第二部分。

先考虑 $|B|\leq |A|$ 的情况，如果一个 $B$ 的左端点是 $x$ ， $A$ 的右端点是 $y$ ，要使得 $B$ 是 $A$ 的前缀的话，一定满足 $lcp(x,y)$ 的长度大于 $|B|$ ，这里 $lcp(x,y)$ 指的是 $str(x,n)$ 和 $str(y,n)$ 的最长公共前缀。

然后考虑建出后缀数组，然后求出 $height$ 数组，现在令 $lcp(x,y)$ 表示排名为 $x$ 的后缀和排名为 $y$ 的后缀的最长公共前缀，然后显而易见的是：
$lcp(l,r)=\min_{i=l+1}^{r}lcp(i,i-1)$
假设当前的 $B$ 的左端点为 $p$ ，其排名为 $k$ ，那么因为跟 $\min$ 有关，在 $rk$ 数组上，其连边区间一定是一段连续的包含 $k$ 的区间，具体的说，就是：

在 $[1,k]$ 中，一定存在一个 $L$ 使得 $\forall i\in[L,k] ,lcp(i,k)\geq |B|$ ， $\forall i\in[1,L-1] ,lcp(i,k)< |B|$ 。
在 $[k,n]$ 中，一定存在一个 $R$ 使得 $\forall i\in[k,R] ,lcp(k,i)\geq |B|$ ， $\forall i\in[R+1,n] ,lcp(k,i)< |B|$ 。

这样的话只需要以 $rk$ 为下标建立线段树，先处理出原串的 $height$ 数组后，对于一个 $|B|$ ，二分一下 $L,R$ ，然后在线段树优化建图即可。

这个是 $80$ 分做法。

对于满分做法，因为不保证 $|A|\geq |B|$ ，所以可能会在 $|A|<|B|$ 但是满足 $lcp$ 条件的情况下从这个 $B$ 往 $A$ 连边，但这个连边是错的。

考虑将 $A,B$ 放在一起，以长度为关键字从大到小排序，对于长度一样的 $A,B$ ，将 $A$ 放在前面。

对于每一个 $A$ ，用可持久化线段树维护。

对于每一个 $B$ ，直接连向当前最后出现的 $A$ 所在版本的线段树对应区间即可。因为同样还要连向更大的 $A$ ，所以可持久化线段树上节点要往其上一版本对应节点连边。

剩下的可持久化线段树上的边无非就是线段树优化建图的同样内容：有儿子往儿子连边，叶子节点往对应的 $A$ 连边即可。

然后注意空间和细节，这道题就没了。

码量主要在后缀数组的板子上？其他的不怎么长（

Code :

代码太长，因此只放部分代码。

若剩下部分需要参考请移步提交记录 https://loj.ac/submission/836201 。

拓扑：

inline ll topsort() {
    for(int i=1;i<=tot;++i) if(!du[i]) que.push(i);
    while(!que.empty()) {
        int u=que.front();que.pop();
        for(auto v:to[u]) {
            chkmax(dp[v],dp[u]+val[u]);
            if(--du[v]==0) que.push(v);
        }
    }
    ll ans=0;
    for(int i=1;i<=tot;++i) if(du[i]) return -1;
    for(int i=1;i<=tot;++i) chkmax(ans,dp[i]+val[i]);
    return ans;
}

可持久化线段树：

int rt[M];
struct Segment_Tree {
    #define mid ((l+r)>>1)
    int lc[N],rc[N];
    void update(int &now,int las,int l,int r,int pos,int tmp) {
        if(!now) now=++tot;
        if(las) addedge(now,las);
        if(l==r) return addedge(now,tmp),void();

        if(pos<=mid) {
            update(lc[now],lc[las],l,mid,pos,tmp);
            addedge(now,lc[now]),rc[now]=rc[las];
        } else {
            update(rc[now],rc[las],mid+1,r,pos,tmp);
            addedge(now,rc[now]),lc[now]=lc[las];
        }
    }
    void Addedge(int now,int l,int r,int L,int R,int id) {
        if(!now) return ;
        if(L<=l&&r<=R) return addedge(id,now),void();
        if(L<=mid) Addedge(lc[now],l,mid,L,R,id);
        if(R>mid) Addedge(rc[now],mid+1,r,L,R,id);
    }
    #undef mid
} seg;

二分：

for(int i=1;i<=cnt;++i) {
    if(q[i].id<=na)
        ++tmp,
        seg.update(rt[tmp],rt[tmp-1],1,n,sa.rk[q[i].pos],q[i].id);
    else {
        k=sa.rk[q[i].pos];
        l=1,r=L=k;
        while(l<=r) (sa.lcp(mid=(l+r)>>1,k)>=q[i].len)?L=mid,r=mid-1:l=mid+1;
        l=R=k,r=n;
        while(l<=r) (sa.lcp(k,mid=(l+r)>>1)>=q[i].len)?R=mid,l=mid+1:r=mid-1;
        if(L<=R) seg.Addedge(rt[tmp],1,n,L,R,q[i].id);
    }
}

【题解】[十二省联考 2019] 字符串问题后缀数组+拓扑+可持久化线段树优化建图 Loj3049 —Qiuly

于2020年6月15日2020年6月15日由Qiuly发布

Code :

拓扑：

可持久化线段树：

二分：

Qiuly

0 条评论

发表回复取消回复

【题解】[十二省联考 2019] 字符串问题 后缀数组+拓扑+可持久化线段树优化建图 Loj3049 —Qiuly

于2020年6月15日2020年6月15日由Qiuly发布

Code :

拓扑：

可持久化线段树：

二分：

Qiuly

0 条评论

发表回复 取消回复

【题解】[十二省联考 2019] 字符串问题后缀数组+拓扑+可持久化线段树优化建图 Loj3049 —Qiuly

发表回复取消回复