题目链接
LOJ：https://loj.ac/problem/3049
洛谷：https://www.luogu.org/problemnew/show/P5284
BZOJ：https://www.lydsy.com/JudgeOnline/problem.php?id=5496
Solution
小清新字符串题
不过小样例是真的强，窝调了一小时样例然后1A了
思路还是很清晰的，首先可以得到一个(O(n^3))的暴力，我们直接大力枚举然后匹配连边，然后( m toposort)求最长连就好了，注意有环就无解。
然后我们大力优化这个暴力就好了，我们用后缀树优化建边，每个子串倍增定位，然后对应到后缀树的点上就好了。
但是这样是不对的，对于(ageqslant b)的情况这样是没有问题的，否则一个点可能有很多(a,b)，那么长度大的(b)不能连向(a)。
所以有两种思路，一是类似虚树的把所有需要用的点都建出来，二是每个点开个( m vector)然后把子串挂在( m vector)上，然后( m sort)之后连边就好了。
复杂度都是(O(nlog n))，下面代码写的是第二种。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
#define ll long long
void print(ll x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(ll x) {if(!x) putchar('0');else print(x);putchar('
');}
#define lf double
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
const int maxn = 8e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
ll dis[maxn];
char s[maxn];
vector<int > t[maxn];
int par[maxn],ml[maxn],tr[maxn][26],lstp=1,stot=1,fa[maxn][20];
int pos[maxn],na,nb,posa[maxn],posb[maxn],len[maxn],is[maxn],lst[maxn],d[maxn];
int head[maxn],tot;
struct edge{int to,nxt;}e[maxn<<1];
void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot,d[v]++;}
int append(int x) {
int p=lstp,np=++stot;lstp=np,ml[np]=ml[p]+1;
for(;p&&tr[p][x]==0;p=par[p]) tr[p][x]=np;
if(!p) return par[np]=1,np;
int q=tr[p][x];
if(ml[q]>ml[p]+1) {
int nq=++stot;ml[nq]=ml[p]+1;
memcpy(tr[nq],tr[q],sizeof tr[nq]);
par[nq]=par[q],par[q]=par[np]=nq;
for(;p&&tr[p][x]==q;p=par[p]) tr[p][x]=nq;
} else par[np]=q;
return np;
}
int cmp(int x,int y) {return len[x]==len[y]?is[x]<is[y]:len[x]<len[y];}
void build() {
scanf("%s",s+1);
for(int n=strlen(s+1),i=n;i;i--) pos[i]=append(s[i]-'a');
for(int i=2;i<=stot;i++) fa[i][0]=par[i];
for(int i=1;i<=18;i++)
for(int j=2;j<=stot;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
read(na);
for(int i=1;i<=na;i++) {
int l,r;read(l),read(r);
int now=pos[l];
for(int j=18;~j;j--) if(ml[fa[now][j]]>=r-l+1) now=fa[now][j];
t[now].push_back(posa[i]=++stot);
len[stot]=r-l+1,is[stot]=1;
}read(nb);
for(int i=1;i<=nb;i++) {
int l,r;read(l),read(r);
int now=pos[l];
for(int j=18;~j;j--) if(ml[fa[now][j]]>=r-l+1) now=fa[now][j];
t[now].push_back(posb[i]=++stot);
len[stot]=r-l+1;
}
for(int x=1;x<=stot;x++) {
int pre=x,L=t[x].size();sort(t[x].begin(),t[x].end(),cmp);
for(int v,i=0;i<L;i++) {
v=t[x][i];add(pre,v);
if(!is[v]) pre=v,len[v]=0;
}lst[x]=pre;
}
for(int x=2;x<=stot;x++) if(par[x]) add(lst[par[x]],x);
int q;read(q);for(int i=1,x,y;i<=q;i++) read(x),read(y),add(posa[x],posb[y]);
}
void solve() {
queue<int > q;ll cnt=0,ans=0;while(!q.empty()) q.pop();
for(int i=1;i<=stot;i++) if(!d[i]) q.push(i);
while(!q.empty()) {
int x=q.front();q.pop();cnt++;
for(int v,i=head[x];i;i=e[i].nxt) {
v=e[i].to;dis[v]=max(dis[v],dis[x]+len[v]);
if(!(--d[v])) q.push(v);ans=max(ans,dis[v]);
}
}write(cnt==stot?ans:-1ll);
}
void clear() {
for(int i=1;i<=stot;i++) {
memset(tr[i],0,sizeof tr[i]);
memset(fa[i],0,sizeof fa[i]);
par[i]=ml[i]=len[i]=dis[i]=d[i]=lst[i]=pos[i]=is[i]=head[i]=0;
t[i].clear();
}tot=0;stot=lstp=1;
}
int main() {
int T;read(T);while(T--) build(),solve(),clear();
return 0;
}