题目大意

给出字符串\(S(|S|\leq2\times10^5)\)，

\(na(na\leq2\times 10^5)\)个区间\([l_i,r_i]\)表示\(S_{l_i},S_{l_i+1},…,S_{r_i}\)组成的这个\(S\)的子串是第\(i\)个A类串

\(nb(nb\leq2\times 10^5)\)个区间\([l_i,r_i]\)表示\(S_{l_i},S_{l_i+1},…,S_{r_i}\)组成的这个\(S\)的子串是第\(i\)个B类串

\(m(m\leq2\times10^5)\)个限制条件\((x,y)\)表示第\(x\)个A类串后面可以接以第\(y\)个B类串为前缀的A类串

现在想要生成字符串\(T\)，满足\(T\)由若干个A类串拼接而成，而且相邻的A类串之间满足限制条件

求\(T\)的最长长度，或判断\(T\)可以无限长

题解

发现将每个A类串看成一个点，点权为它的长度，将每个A类串向它后面能接的A类串连边

问题就变成了找环或求点权之和最大的链

暴力连边肯定不行，考虑后缀树优化建图

连出的边的形态大概是：\(A_i->B_i->以B_i为前缀的A\)

那么考虑将后缀树上的每个点\(x\)拆成两个点\(x_A,x_B\)

要连的边就是：\(x_B->x_A,x_{A_i}->x_{B_i}\)和从\(x_B\)连向它后缀树的儿子的\(x_B\)的边

还有个问题：已知区间\([l,r]\)，在\(S\)的后缀树中找到\(S[l:r]\)对应的点

后缀树中每个叶子结点是\(S\)的后缀，父亲是儿子的前缀

那么对于\(\forall i\in[1,|S|]\)可以在建后缀树时记\(S[i:|S|]\)的位置

找\(S[l:r]\)对应的位置就变成了先找\(S[l:|S|]\)的位置，再在这个点的祖先中找到\(dis\)值不小于\(r-l+1\)的最高点

这一步可以预处理每个点第\(2^k\)个祖先+倍增

还有一点要注意的是，后缀树中的每个点可能代表了多个串，所以还要再把每个点内部拆一次

并没有想象中那么难写

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 200010
#define maxm (maxn<<1)
#define LL long long
#define pb push_back
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
void write(LL x)
{
    if(x==0){putchar('0'),putchar('\n');return;}
    int f=0;char ch[20];
    if(x<0)putchar('-'),x=-x;
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
    return;
}
char s[maxn];
int dfn[maxm<<2],in[maxm<<2],yes,n,ch[maxm][26],dis[maxm],fa[maxm],posa[maxn],posb[maxn],pos[maxn],rt,cntnd,lst,c[maxn],ord[maxm];
int m,T,na,nb,fir[maxm<<2],nxt[maxm<<3],v[maxm<<3],cnte,anc[maxm][20],low[maxm<<2],ins[maxm<<2],tim,stk[maxm<<2],tp,tot;
int Q[maxm<<2],hd,tl,ltha[maxn],lthb[maxn];
LL maxd[maxm<<2],ans;
int w[maxm<<2];
vector <int >val[maxm],id[maxm];
#define gx(C) (C-'a')
void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
void ext(int i)
{
    int p=lst,val=gx(s[i]),np=++cntnd;dis[np]=i,lst=np,pos[n-i+1]=np;
    for(;p&&!ch[p][val];p=fa[p])ch[p][val]=np;
    if(!p)fa[np]=rt;
    else
    {
        int q=ch[p][val];
        if(dis[p]+1==dis[q])fa[np]=q;
        else
        {
            int nq=++cntnd;
            dis[nq]=dis[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for(;p&&ch[p][val]==q;p=fa[p])ch[p][val]=nq;
        }
    }
}
void reset()
{
    rep(i,1,n)c[i]=0;
    rep(i,1,cntnd)rep(j,0,25)ch[i][j]=0;
    rep(i,1,cntnd)rep(j,0,19)anc[i][j]=0;
    rep(i,1,cntnd){fa[i]=0;}
    dwn(i,(tot<<1),1)dfn[i]=in[i]=maxd[i]=0,fir[i]=-1,w[i]=0;
    rt=lst=cntnd=hd=1;tl=cnte=yes=ans=tim=tp=tot=0;
}
int getp(int l,int r)
{
    int len=r-l+1,u=pos[l];
    dwn(i,19,0)if(anc[u][i]&&dis[anc[u][i]]>=len)u=anc[u][i];
    return u;
}
void tar(int u)
{
    dfn[u]=low[u]=++tim;
    ins[u]=1,stk[++tp]=u;
    view(u,k)
    {
        if(!dfn[v[k]])tar(v[k]),low[u]=min(low[u],low[v[k]]);
        else if(ins[v[k]])low[u]=min(low[u],dfn[v[k]]);
    }
    if(low[u]==dfn[u])
    {
        int num=0;
        while(1)
        {
            num++;
            ins[stk[tp]]=0;
            if(stk[tp--]==u)break;
        }
        if(num>1)yes=1;
    }
}
int getpos(int u,int len)
{
    int l=0,r=val[u].size()-1,res=r;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(val[u][mid]>=len)res=min(res,mid),r=mid-1;
        else l=mid+1;
    }
    return id[u][res];
}
int main()
{
    T=read();
    memset(fir,-1,sizeof(fir));rt=lst=++cntnd;hd=1,tl=0;
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        reverse(s+1,s+n+1);
        rep(i,1,n)ext(i);
        rep(i,1,cntnd)c[dis[i]]++;
        rep(i,1,n)c[i]+=c[i-1];
        rep(i,1,cntnd)ord[c[dis[i]]--]=i;
        rep(j,1,cntnd)
        {
            int i=ord[j];
            anc[i][0]=fa[i];
            rep(k,1,19)anc[i][k]=anc[anc[i][k-1]][k-1];
        }
        na=read();
        rep(i,1,na){int l=read(),r=read();posa[i]=getp(l,r),val[posa[i]].pb(r-l+1),ltha[i]=r-l+1;}
        nb=read();
        rep(i,1,nb){int l=read(),r=read();posb[i]=getp(l,r),lthb[i]=r-l+1;}
        rep(i,1,cntnd)sort(val[i].begin(),val[i].end());
        rep(j,1,cntnd)
        {
            int lim=val[ord[j]].size(),Lst=0;if(fa[ord[j]]){Lst=id[fa[ord[j]]][id[fa[ord[j]]].size()-1];}
            rep(k,0,lim-1){++tot,w[tot]=val[ord[j]][k];if(fa[ord[j]])ade(Lst,tot),++in[tot];Lst=tot,id[ord[j]].pb(tot);}
            if(!lim||val[ord[j]][lim-1]!=dis[ord[j]]){++tot;if(fa[ord[j]])ade(Lst,tot),++in[tot];id[ord[j]].pb(tot);val[ord[j]].pb(dis[ord[j]]);}
        }
        m=read();
        rep(i,1,tot)ade(i,i+tot),++in[i+tot],w[i+tot]=w[i],w[i]=0;
        rep(i,1,m)
        {
            int x=read(),y=read();
            x=getpos(posa[x],ltha[x]),y=getpos(posb[y],lthb[y]);
            ade(x+tot,y),in[y]++;
        }
        {rep(i,1,cntnd){val[i].clear(),val[i].shrink_to_fit();id[i].clear(),id[i].shrink_to_fit();}}
        dwn(i,(tot<<1),1)if(!dfn[i])tar(i);
        if(yes)puts("-1");
        else
        {
            dwn(i,(tot<<1),1)if(!in[i])Q[++tl]=i;
            while(hd<=tl)
            {
                int u=Q[hd++];maxd[u]+=w[u],ans=max(ans,maxd[u]);
                view(u,k)
                {
                    maxd[v[k]]=max(maxd[v[k]],maxd[u]),in[v[k]]--;
                    if(!in[v[k]])Q[++tl]=v[k];
                }
            }
            write(ans);
        }
        reset();
    }
    return 0;
}

一些感想

据说猎人公会会长是云猎人。。。我佛了

sb猎人公会nmsl