大致题意： 给你一个字符串，从中划出\(n_a\)个子串作为\(A\)类串，\(n_b\)个子串作为\(B\)类串。已知\(m\)组支配关系，让你求出一个字符串，使得它由若干\(A\)类串依次相接组成，且每个\(A\)类串存在一个被其支配的\(B\)类串是它的后一个串的前缀。输出最长字符串长度，无限长输出\(-1\)。

核心思路

首先，我们来想一下这题的核心思路应该是什么。

显然，不难想到可以把它看成一张\(DAG\)，则每个\(A\)类串向其支配的\(B\)类串连边，每个\(B\)类串向以其为前缀的\(A\)类串连边。每个\(A\)类串权值为自身长度，每个\(B\)类串权值为\(0\)，最后拓扑排序求一遍权值和最大的路径的权值和即为答案。

但这样具体实现起来有些困难。

仔细观察上述内容，可以发现我们共要连两种边：

• 每个\(A\)类串向其支配的\(B\)类串连边。
• 每个\(B\)类串向以其为前缀的\(A\)类串连边。

其中第一种边边数已知为\(m\)，可以直接连。

但第二种边该如何处理，就是我们主要讨论的问题。

利用后缀数组进行转化

首先，我们对给出的这个字符串建一个。

考虑如果一个\(B\)类串是一个\(A\)类串的前缀，则这两个串的\(LCP\)必然会等于\(len_B\)。

而移到后缀数组上，就等价于后缀\(_{l_B}\)与后缀\(_{l_A}\)的\(LCP\ge len_B\)。

又因为关于\(LCP\)的一个定理：\(LCP(i,j)=min_{k=i+1}^jLCP(k,k−1)\)，所以后缀\(_{l_B}\)在后缀排序后与其他后缀的\(LCP\)是向左右两侧递减的。

而后缀\(_{l_B}\)在后缀排序后的位置是\(rk_{l_B}\)，因此我们考虑在\(1\sim rk_{l_B}\)和\(rk_{l_B}\sim n\)两个范围内各二分求出离\(l_B\)最远且满足与后缀\(_{l_B}\)的\(LCP\ge len_B\)的位置\(L,R\)。

那么，我们就要从这个\(B\)类串向\([L,R]\)区间内所有点连边。

这看起来似乎可以直接线段树优化建图。

但是，我们要考虑，当\(A\)类串与\(B\)类串的长度满足\(|A|<|B|\)时，这个\(B\)类串是不能算作这个\(A\)类串的前缀的！

问题一下棘手了许多。

因此，就需要主席树优化建图了。

主席树优化建图

关于主席树，可以看这篇博客：。

我们考虑，以字符串的长度为版本建主席树。

对于\(A\)类串，从它在版本\(len_A\)的树中其\(rk\)值对应的节点向其连一条边。

对于\(B\)类串，从它向版本\(len_B\)的树中\([L,R]\)内的节点连边（注意这里可以采取类似懒惰标记的形式向区间连边，使得边数被控制在\(2*logN\)）。

主席树与主席树之间，我们按\(len\)从大到小建树，然后同一个位置上的节点每次从\(len\)小的向\(len\)大的连边（因为我们要\(|A|\ge|B|\)，所以只能向\(|A|\)更大的走）。

同一棵主席树上，我们从父节点向子节点连边。

再加上之前提到过的每个\(A\)类串向其支配的\(B\)类串连边，建图就完成了。

复杂度分析

最后我们来分析一下复杂度，由于\(|S|,na,nb,m\)全部同阶，我们用\(N\)来替代它们。

• 点数：\(A\)类串个数\(N+B\)类串个数\(N+\)主席树上点的个数\(NlogN=2N+NlogN\)。
• 边数：\(A\)类串向\(B\)类串\(N+\)主席树向\(A\)类串\(N+B\)类串向主席树\(2NlogN+\)主席树间\(NlogN+\)主席树上\(NlogN=2N+4NlogN\)。
• 时间复杂度：\(O(TNlogN)\)。

具体实现详见代码。

代码

#include
    
     #define Tp template
     
      #define Ts template
      
       #define Reg register#define RI Reg int#define Con const#define CI Con int&#define I inline#define W while#define N 200000#define Log 20#define LL long long#define min(x,y) ((x)<(y)?(x):(y))#define Gmax(x,y) (x<(y)&&(x=(y)))#define add(x,y) (e[++ee].nxt=lnk[x],++deg[e[lnk[x]=ee].to=y])#define Pt (N*2+N*Log)#define Et (N*2+N*Log*4)#define mem(x,v) memset(x,v,sizeof(x))using namespace std;int na,nb,m,ee,tot,la[N+5],ra[N+5],lb[N+5],rb[N+5],lnk[Pt+5],deg[Pt+5],q[Pt+5],v[Pt+5];LL f[Pt+5];struct edge {int to,nxt;}e[Et+5];string s;struct Pr{    int len,id;I Pr(CI x=0,CI y=0):len(x),id(y){}    I bool operator < (Con Pr& o) Con {return len>o.len;}}p[N+5];class FastIO{    private:        #define FS 100000        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)        #define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))        #define tn (x<<3)+(x<<1)        #define D isdigit(c=tc())        int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];    public:        I FastIO() {A=B=FI;}        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}        Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}        Tp I void writeln(Con Ty& x) {write(x),pc('\n');}        I void reads(string& x) {x="";W(isspace(c=tc()));W(x+=c,!isspace(c=tc())&&~c);}        I void clear() {fwrite(FO,1,C,stdout),C=0;} }F;class ChairmanTree//主席树优化建图{    private:        #define L l,mid,O[rt].S[0]        #define R mid+1,r,O[rt].S[1]        int n,v,Rt_[N+5],Rt[N+5];struct node {int S[2];}O[Pt+5];        I int ins(CI l,CI r,int& rt,CI lst,CI x)//插入新节点        {            if(O[rt=++tot]=O[lst],lst&&add(rt,lst),!(l^r)) return rt;RI mid=l+r>>1;//向上一个节点连边；返回叶节点编号            RI g=x<=mid?ins(L,O[lst].S[0],x):ins(R,O[lst].S[1],x);//处理子节点            return O[rt].S[0]&&add(rt,O[rt].S[0]),O[rt].S[1]&&add(rt,O[rt].S[1]),g;//向子节点建边        }        I void adde(CI l,CI r,CI rt,CI p,CI tl,CI tr)//建边        {            if(!rt) return;if(tl<=l&&r<=tr) return (void)add(p,rt);RI mid=l+r>>1;//空节点直接返回；建边类似于懒惰标记，向这一区间建边            tl<=mid&&(adde(L,p,tl,tr),0),tr>mid&&(adde(R,p,tl,tr),0);//处理子节点        }    public:        I void Init(CI x) {n=x;}I void CopyRoot(CI x,CI y) {Rt[x]=Rt[y];}        I void Clear() {v=0,mem(Rt_,0),mem(Rt,0);for(RI i=1;i<=tot;++i) O[i].S[0]=O[i].S[1]=0;}//清空（注意清空版本数！）        I int Insert(CI t,CI x) {RI g;return ++v,g=ins(1,n,Rt_[v],Rt_[v-1],x),Rt[t]=Rt_[v],g;}        I void AddEdge(CI t,CI p,CI l,CI r) {adde(1,n,Rt[t],p,l,r);}        #undef R}C;class SuffixArray//后缀数组{    private:        #define LCP(x,y) (x
       
        >1]+1;                    for(j=1;(1<
        
         <=x;++j) for(i=1;i+(1<
         
          <=x;++i) Mn[i][j]=min(Mn[i][j-1],Mn[i+(1<
          
           k&&(p[++t]=SA[i]-k); for(Rsort(S),i=1;i<=n;++i) p[i]=rk[i]; for(rk[SA[1]]=t=1,i=2;i<=n;++i) rk[SA[i]]= (p[SA[i-1]]^p[SA[i]]||p[SA[i-1]+k]^p[SA[i]+k])?++t:t; } } I void GetH(Con string& s)//求Height数组用于LCP { RI i,j,k=0;for(i=1;i<=n;++i) rk[SA[i]]=i; for(i=1;i<=n;++i) { if(k&&--k,rk[i]==1) continue;j=SA[rk[i]-1]; W(i+k<=n&&j+k<=n&&!(s[i+k-1]^s[j+k-1])) ++k;H[rk[i]]=k; } } public: int rk[N+5]; I void Init(CI x,Con string& s) {n=x,GetSA(s),GetH(s),R.Init(n,H);} I void Work(CI x)//处理第x个B类串 { RI i,t=rk[lb[x]],l1,r1,l2,r2,mid,len=rb[x]-lb[x]+1; l1=1,r1=t;W(l1
           
            >1,LCP(mid,t)>=len?r1=mid:l1=mid+1;//二分1~t l2=t,r2=n;W(l2
            
             >1,LCP(t,mid)>=len?l2=mid:r2=mid-1;//二分t~n C.AddEdge(len,na+x,r1,l2);//向区间连边 }}S;I LL Topo()//拓扑排序+DP求答案{ RI i,k,H=1,T=0;Reg LL ans=0;for(i=1;i<=na;++i) f[i]=v[i]=ra[i]-la[i]+1;//初始化权值 for(i=1;i<=tot;++i) !deg[i]&&(q[++T]=i);//初始化队列 W(H<=T) for(i=lnk[k=q[H++]],Gmax(ans,f[k]);i;i=e[i].nxt)//取出队首，统计答案，枚举转移 Gmax(f[e[i].to],f[k]+v[e[i].to]),!--deg[e[i].to]&&(q[++T]=e[i].to);//转移，判断是否加入队列 return T^tot?-1:ans;//如果队列中点数与总点数不符，返回-1，否则返回ans}int main(){ RI Ttot,i,t,x,y,l;F.read(Ttot);W(Ttot--) { ee=0,mem(lnk,0),mem(deg,0),mem(f,0),mem(v,0),C.Clear(),//注意清空 F.reads(s),C.Init(l=s.length()),S.Init(l,s);//初始化 for(F.read(na),i=1;i<=na;++i) F.read(la[i],ra[i]),p[i]=Pr(ra[i]-la[i]+1,i);//读入，将每个A类串按长度和编号存下来 for(F.read(nb),tot=na+nb,sort(p+1,p+na+1),t=1,i=l;i;--i)//排序，枚举版本 { C.CopyRoot(i,i+1);W(t<=na&&p[t].len==i)//建该版本的树 x=C.Insert(p[t].len,S.rk[la[p[t].id]]),add(x,p[t].id),++t;//建完后记得连边 } for(i=1;i<=nb;++i) F.read(lb[i],rb[i]),S.Work(i);//处理B类串 for(F.read(m),i=1;i<=m;++i) F.read(x,y),add(x,na+y);F.writeln(Topo());//根据支配关系连边，然后输出答案 }return F.clear(),0;}