题面
https://www.luogu.org/problem/P5284
题解
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<algorithm> #define ri register int #define N 200050 using namespace std; int ff[N<<1],ch[N<<1][26],len[N<<1]; int fa[N<<1][21],poi[N],p[N]; int las,tot,cnt; int Na,Nb,m; char s[N]; int lb[N<<1],rb[N<<1]; int LLL[N]; int msiz; vector<int> son[N<<1],to[N*5],ll[N*5]; long long f[N*5]; struct node { int l,id; bool operator < (const node &rhs) const { return l<rhs.l; } }; vector<node> in[N<<1]; node a[N]; void extend(int c){ int p=las,np=++tot; las=np; len[np]=len[p]+1; poi[len[np]]=np; while (p && ch[p][c]==0) ch[p][c]=np,p=ff[p]; if (!p) ff[np]=1; else { int q=ch[p][c]; if (len[q]==len[p]+1) ff[np]=q; else { int nq=++tot; for (ri i=0;i<26;i++) ch[nq][i]=ch[q][i]; ff[nq]=ff[q]; len[nq]=len[p]+1; ff[np]=ff[q]=nq; while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p]; } } } void init(int x) { fa[x][0]=ff[x]; for (ri i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for (ri i=0;i<son[x].size();i++) init(son[x][i]); } int find(int l,int r) { int x=poi[r]; for (ri i=20;i>=0;i--) if (len[fa[x][i]]>=r-l+1) x=fa[x][i]; return x; } void dfs(int x) { lb[x]=cnt+1; for (ri i=0;i<in[x].size();i++) a[++cnt]=in[x][i]; for (ri i=0;i<son[x].size();i++) dfs(son[x][i]); rb[x]=cnt; } void maketree(int now,int l,int r){ if(l==r) { p[a[l].id]=now; to[now].push_back(200050*5-1); ll[now].push_back(a[l].l); msiz=max(msiz,now); return; } int mid=(l+r)/2; to[now].push_back(now<<1); ll[now].push_back(0); to[now].push_back(now<<1|1); ll[now].push_back(0); maketree(now<<1,l,mid); maketree(now<<1|1,mid+1,r); } void link(int a,int now,int lb,int rb,int l,int r) { if (l>r) return; if (l<=lb && rb<=r) { to[a].push_back(now); ll[a].push_back(0); return; } if (l>rb || r<lb) return; int mid=(lb+rb)/2; link(a,now<<1,lb,mid,l,r); link(a,now<<1|1,mid+1,rb,l,r); } bool dp(int x) { if (f[x]==-1) return true; if (f[x]!=0) return false; f[x]=-1; long long rye=0; for (ri i=0;i<to[x].size();i++) { if (dp(to[x][i])) return true; if (f[to[x][i]]+ll[x][i]>rye) rye=f[to[x][i]]+ll[x][i]; } f[x]=rye; return 0; } void solve(){ int x,y; las=tot=1; scanf("%s",s+1); int L=strlen(s+1); for (ri i=L;i>=1;i--) extend(s[i]-'a'); for (ri i=1;i<=tot;i++) son[ff[i]].push_back(i); init(1); scanf("%d",&Na); for (ri i=1;i<=Na;i++) { scanf("%d %d",&x,&y); x=L-x+1; y=L-y+1; LLL[i]=x-y+1; in[find(y,x)].push_back((node){x-y+1,i}); } for (ri i=1;i<=tot;i++) sort(in[i].begin(),in[i].end()); cnt=0;dfs(1);msiz=0;maketree(1,1,Na); scanf("%d",&Nb); for (ri i=1;i<=Nb;i++) { scanf("%d %d",&x,&y); x=L-x+1; y=L-y+1; int pr=find(y,x); //int cant=lower_bound(in[pr].begin(),in[pr].end(),(node){x-y+1,-1})-in[pr].begin(); int L0=0,R0=in[pr].size()-1; int ret=-1; while (L0<=R0) { int mid=(L0+R0)/2; if (in[pr][mid].l<x-y+1) ret=mid,L0=mid+1; else R0=mid-1; } int cant=ret+1; link(i+msiz,1,1,Na,lb[pr]+cant,rb[pr]); } scanf("%d",&m); for (ri i=1;i<=m;i++) { scanf("%d %d",&x,&y); to[p[x]].push_back(y+msiz); ll[p[x]].push_back(LLL[x]); } long long ans=0; for (ri i=1;i<=msiz+Nb;i++) { if (!f[i] && dp(i)) { puts("-1"); return; } if (f[i]>ans) ans=f[i]; } printf("%lld ",ans); } int main() { int T; scanf("%d",&T); while (T--) { solve(); for (ri i=1;i<=tot;i++) { for (ri j=0;j<26;j++) ch[i][j]=0; son[i].clear(); in[i].clear(); } for (ri i=1;i<=msiz+Nb;i++) to[i].clear(),ll[i].clear(),f[i]=0; } return 0; }