题意
内存限制：1024 MiB
时间限制：5000 ms
现有一个字符串 $S$。
Tiffany 将从中划出 $n_a$ 个子串作为 A 类串，第 $i$ 个（$1leq ileq n_a$）为 $A_i = Sleft( la_i, ra_i ight)$。
类似地，Yazid 将划出 $n_b$ 个子串作为 B 类串，第 $i$ 个（$1leq ileq n_b$）为 $B_i = Sleft( lb_i, rb_i ight)$。
现额外给定 $m$ 组支配关系，每组支配关系 $left( x,y ight)$ 描述了第 $x$ 个 A 类串**支配**第 $y$ 个 B 类串。
求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T=t_1 + t_2 +dots +t_k$（$kgeq 0$）满足：
- 分割中的每个串 $t_i$ 均为 A 类串：即存在一个与其相等的 A 类串，不妨假设其为 $t_i = A_{id_i}$。
- 对于分割中所有相邻的串 $t_i , t_{i+1}$（$1leq i < k$），都有存在一个 $A_{id_i}$ 支配的 B 类串，使得该 B 类串为 $t_{i+1}$ 的前缀。
方便起见，你只需要输出这个最大的长度即可。
特别地，如果存在无限长的目标串（即对于任意一个正整数 $n$，都存在一个满足限制的长度超过 $n$ 的串），请输出 $-1$。
$1leq lvert S
vertleq 2 imes 10^5$，$n_a , n_bleq 2 imes 10^5$，$mleq 2 imes 10^5$
题解
数据千万条，清空第一条。
多测不清空，爆零两行泪。
题意大概就是将A往支配的B连边，B往它作为前缀的A连边的最长路
对于后一部分我们可以反串后建立SAM，建立parent树，然后对于A，B利用倍增找到它所对应的节点
这样可能一个节点对应很多个A和B，所以在每个节点上我们对其按照长度排序，然后B往下一个B连边，A向长度小于等于它的第一个B连反向边，特别的我们可以设立一个特殊点，使其作为B的功能且长度最短
然后对于parent树上的父亲和儿子节点，我们将父亲长度最长的B和儿子的特殊点相连
跑拓扑即可
#include <bits/stdc++.h> using namespace std; const int N=2e6+5;long long ans,dis[N]; int T,fa[N][20],len[N],lst,sz,n,id[N],na,nb,a[N]; int b[N],cnt,t,hd[N],d[N],V[N],nx[N],h[N],m,ch[N][26]; char s[N];bool isa[N];vector<int>g[N];queue<int>q; void add(int u,int v){ nx[++t]=hd[u];d[V[hd[u]=t]=v]++; } int init(int x){ len[++sz]=x;fa[sz][0]=isa[sz]=0; memset(ch[sz],0,sizeof ch[sz]);return sz; } void build(int x){ int p=lst,np=init(len[p]+1); while(p && !ch[p][x]) ch[p][x]=np,p=fa[p][0]; if (!p) fa[np][0]=1; else{ int q=ch[p][x]; if (len[q]==len[p]+1) fa[np][0]=q; else{ int nq=init(len[p]+1); fa[nq][0]=fa[q][0]; memcpy(ch[nq],ch[q],sizeof ch[q]); fa[q][0]=fa[np][0]=nq; while(p && ch[p][x]==q) ch[p][x]=nq,p=fa[p][0]; } } lst=np; } void find(bool ty){ int x,y;scanf("%d%d",&x,&y); y=y-x+1;x=id[x]; for (int i=18;~i;i--) if (len[fa[x][i]]>=y) x=fa[x][i]; isa[++cnt]=ty;len[cnt]=y; g[x].push_back(cnt); } bool cmp(int A,int B){ return len[A]>len[B]||(len[A]==len[B]&&isa[A]>isa[B]); } int main(){ for (scanf("%d",&T);T--;ans=0){ scanf("%s",s+1);n=strlen(s+1);sz=0;lst=init(0); for (int i=n;i;i--) build(s[i]-'a'),id[i]=lst; for (int j=1;(1<<j)<=sz;j++) for (int i=1;i<=sz;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; for (int i=1;i<=sz;i++) g[i].clear();cnt=sz; scanf("%d",&na);for (int i=1;i<=na;i++) find(1),a[i]=cnt; scanf("%d",&nb);for (int i=1;i<=nb;i++) find(0),b[i]=cnt; for (int i=1;i<=sz;i++) sort(g[i].begin(),g[i].end(),cmp); for (int i=1;i<=cnt;i++) hd[i]=d[i]=dis[i]=0;t=0; for (int pr,i=1;i<=sz;i++){ pr=i; for (int v,j=g[i].size()-1;~j;j--){ v=g[i][j];add(pr,v); if (!isa[v]) pr=v; }h[i]=pr; } for (int i=2;i<=sz;i++) add(h[fa[i][0]],i); scanf("%d",&m);for (int x,y,i=1;i<=m;i++) scanf("%d%d",&x,&y),add(a[x],b[y]); for (int i=1;i<=cnt;i++){ if (!d[i]) q.push(i);if (!isa[i]) len[i]=0; } while(!q.empty()){ int x=q.front();q.pop(); ans=max(ans,dis[x]+len[x]); for (int i=hd[x];i;i=nx[i]){ dis[V[i]]=max(dis[V[i]],dis[x]+len[x]); d[V[i]]--;if (!d[V[i]]) q.push(V[i]); } } for (int i=1;i<=cnt;i++) if (d[i]){puts("-1");goto out;} printf("%lld ",ans);out:; }return 0; }