题目：

每个 b 找出它是哪些 a 的前缀，然后就可以让一些 a 向另一些 a 连边，这个图找最长路即可。

b 找它是哪些 a 的前缀的时候，可以做出后缀数组，然后二分一下 LCP >= lenb 的范围，范围内的 a 就是可以连边的（如果 |a|>=|b|）。

边数可能 n² ，但注意到一个 b 导致的连边是一个区间内的 a ，所以考虑线段树优化连边。

但考场上觉得太难写了，就只写了暴力连边的 40 分。结果得了 0 分。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define pb push_backusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
     return a>b?a:b;}ll Mn(ll a,ll b){
     return a
           
            b.l:r
            
              vt[M]; queue
             
               q; void init() { xnt=0;for(int i=1;i<=na;i++)hd[i]=rd[i]=0; flag=0;for(int i=1;i<=na;i++)vis[i]=ins[i]=0; for(int i=1;i<=na;i++)vt[i].clear();// } void add(int x,int y,int z) {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;rd[y]++;} void Rsort(int n,int nm) { for(int i=1;i<=nm;i++)tx[i]=0; for(int i=1;i<=n;i++)tx[rk[i]]++; for(int i=2;i<=nm;i++)tx[i]+=tx[i-1]; for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i]; } void get_sa(int n,int nm) { for(int i=1;i<=n;i++)rk[i]=s[i]-'a'+1,tp[i]=i; Rsort(n,nm); for(int k=1;k<=n;k<<=1) { int tot=0; for(int i=n-k+1;i<=n;i++)tp[++tot]=i; for(int i=1;i<=n;i++) if(sa[i]>k)tp[++tot]=sa[i]-k; Rsort(n,nm); for(int i=1;i<=n;i++)tp[i]=rk[i]; rk[sa[1]]=nm=1; for(int i=2;i<=n;i++) { int u=sa[i]+k,v=sa[i-1]+k; if(u>n)u=0;if(v>n)v=0; rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm; } if(nm==n)break; } } void get_ht(int n) { for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; bin[0]=1; for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1; for(int i=1,k=0,j;i<=n;i++)//k=0 { for((k?k--:0),j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++); ht[rk[i]][0]=k; } for(int t=1;t<=lg[n];t++) for(int i=1;i+bin[t]-1<=n;i++) ht[i][t]=Mn(ht[i][t-1],ht[i+bin[t-1]][t-1]); } int qry_ht(int l,int r) { if(l==r)return n-sa[l]+1; if(l>r)swap(l,r); l++; int d=lg[r-l+1]; return Mn(ht[l][d],ht[r-bin[d]+1][d]); } void solve2() { int m=rdn(); while(m--)rdn(), rdn(); int cr=rk[a[1].l]; for(int i=1;i<=nb;i++) if(qry_ht(cr,b[i].l)>=b[i].r-b[i].l+1) {flag=1;break;} if(flag)puts("-1"); else printf("%d\n",a[1].r-a[1].l+1); } Node cz(int p,int len) { Node ret; p=rk[p];//rk int l=1,r=p,ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,r=mid-1; else l=mid+1; } ret.l=ans; l=p; r=n; ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,l=mid+1; else r=mid-1; } ret.r=ans; return ret; } void sol(int bh) { sort(vt[bh].begin(),vt[bh].end()); int top=0; for(int i=0,lm=vt[bh].size();i
              
               =vt[bh][i].l)top--; if(!top||sta[top].r
              
             
            
           
          
         
        
       
      

发现自己很多细节都写错了。

1. vis[ ] 有用在整个字符串范围上，所以大小应该是 N 而不是 M （倒是那个 rd[ ] ，大小是 M 即可）。并且配套的，在 init( ) 的时候要 1~n 的 vis[ ]=0 而不是 1~na 的 vis[ ]=0 ；

2.拓扑找开头的时候顺便赋初值，不是只有开头才赋初值，而是每个点都要 dis[ ] = r-l+1 ，因为自己的 init( ) 里没有管 dis ；

改了这两处就能有 10 分了。

3. log 的大小，即 K 的大小，不是 log 1000 ，而是 log 2e5 ，所以 K 不是 15 而是 20 ；

4.b[ ] 以及相关的 fw[ ] , sta[ ] 的大小不是 M 而是 N ；

5.在 na==1 的特判里，有一个 qry_ht( cr , b[ i ].l ) ，那里应该是 qry_ht( cr , rk[ b[ i ].l ] ) 。

改掉这些就能得到预计的 40 分啦……

错误主要是：数组大小、初值处理、手误。在写代码的时候应该更用心。

现在的代码交到洛谷上，只能过第 4 个点；但本地测的是 40 分。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define pb push_backusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
     return a>b?a:b;}ll Mn(ll a,ll b){
     return a
           
            b.l:r
            
              vt[M]; queue
             
               q; void init() { xnt=0;for(int i=1;i<=na;i++)hd[i]=rd[i]=0; flag=0;for(int i=1;i<=na;i++)ins[i]=0; for(int i=1;i<=n;i++)vis[i]=0;//n not na for(int i=1;i<=na;i++)vt[i].clear();// } void add(int x,int y,int z) {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;rd[y]++;} void Rsort(int n,int nm) { for(int i=1;i<=nm;i++)tx[i]=0; for(int i=1;i<=n;i++)tx[rk[i]]++; for(int i=2;i<=nm;i++)tx[i]+=tx[i-1]; for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i]; } void get_sa(int n,int nm) { for(int i=1;i<=n;i++)rk[i]=s[i]-'a'+1,tp[i]=i; Rsort(n,nm); for(int k=1;k<=n;k<<=1) { int tot=0; for(int i=n-k+1;i<=n;i++)tp[++tot]=i; for(int i=1;i<=n;i++) if(sa[i]>k)tp[++tot]=sa[i]-k; Rsort(n,nm); for(int i=1;i<=n;i++)tp[i]=rk[i]; rk[sa[1]]=nm=1; for(int i=2;i<=n;i++) { int u=sa[i]+k,v=sa[i-1]+k; if(u>n)u=0;if(v>n)v=0; rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm; } if(nm==n)break; } } void get_ht(int n) { for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; bin[0]=1; for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1; for(int i=1,k=0,j;i<=n;i++)//k=0 { for((k?k--:0),j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++); ht[rk[i]][0]=k; } for(int t=1;t<=lg[n];t++) for(int i=1;i+bin[t]-1<=n;i++) ht[i][t]=Mn(ht[i][t-1],ht[i+bin[t-1]][t-1]); } int qry_ht(int l,int r) { if(l==r)return n-sa[l]+1; if(l>r)swap(l,r); l++; int d=lg[r-l+1]; return Mn(ht[l][d],ht[r-bin[d]+1][d]); } void solve2() { int m=rdn(); while(m--)rdn(), rdn(); int cr=rk[a[1].l]; for(int i=1;i<=nb;i++) if(qry_ht(cr,rk[b[i].l])>=b[i].r-b[i].l+1)//rk[]!!!! {flag=1;break;} if(flag)puts("-1"); else printf("%d\n",a[1].r-a[1].l+1); } Node cz(int p,int len) { Node ret; p=rk[p];//rk int l=1,r=p,ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,r=mid-1; else l=mid+1; } ret.l=ans; l=p; r=n; ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,l=mid+1; else r=mid-1; } ret.r=ans; return ret; } void sol(int bh) { sort(vt[bh].begin(),vt[bh].end()); int top=0; for(int i=0,lm=vt[bh].size();i
              
               =vt[bh][i].l)top--; if(!top||sta[top].r
              
             
            
           
          
         
        
       
      

 上面的代码其实还是爆零的……

那个 tx[ ] 的大小应该是 N 而不是字符集大小！！！因为之后 rk[ ] 就会变成 N 。如果不开 O2 ，好像测的没问题，但开 O2 就会爆零了。

80 分的代码就是线段树优化连边。其实没有想象的复杂，不用建两个线段树之类的，因为是有向边。

线段树的父亲向孩子连边，叶子向它要连的区间节点连边。

自己的方法是把 a 排序，二分出 b 在 sa 数组上的控制范围（是对 sa 角标的而非对 a 的范围，不然判断麻烦），再在线段树上一边走一边看范围。注意判断一下如果 l==r 都不合法就要及时 return 。

本地开了 O2 测得 80 。交到洛谷上还是只能过第 4 个点，不知为何。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define pb push_back#define ls Ls[cr]#define rs Rs[cr]using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
     return a>b?a:b;}ll Mn(ll a,ll b){
     return a
           
            b.l:r
            
             k)tp[++tot]=sa[i]-k; Rsort(n,nm); for(int i=1;i<=n;i++)tp[i]=rk[i]; rk[sa[1]]=nm=1; for(int i=2;i<=n;i++) { int u=sa[i]+k,v=sa[i-1]+k; if(u>n)u=0;if(v>n)v=0; rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm; } if(nm==n)break; }}void get_ht(int n){ for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; bin[0]=1; for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1; for(int i=1,k=0,j;i<=n;i++)//k=0 { for((k?k--:0),j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++); ht[rk[i]][0]=k; } for(int t=1;t<=lg[n];t++) for(int i=1;i+bin[t]-1<=n;i++) ht[i][t]=Mn(ht[i][t-1],ht[i+bin[t-1]][t-1]);}int qry_ht(int l,int r){ if(l==r)return n-sa[l]+1; if(l>r)swap(l,r); l++; int d=lg[r-l+1]; return Mn(ht[l][d],ht[r-bin[d]+1][d]);}Node cz(int p,int len){ Node ret; p=rk[p];//rk int l=1,r=p,ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,r=mid-1; else l=mid+1; } ret.l=ans; l=p; r=n; ans=p; while(l<=r) { int mid=l+r>>1; if(qry_ht(mid,p)>=len)ans=mid,l=mid+1; else r=mid-1; } ret.r=ans; return ret;}namespace S2{ const int M=N<<1,M2=7600005; int tot,Ls[M],Rs[M],c[M],ps[N]; int hd[M],xnt,to[M2],nxt[M2],rd[M]; ll dis[M]; bool vis[M],ins[M],flag; vector
             
               vt[N]; queue
              
                q; bool cmp(Node u,Node v){ return rk[u.l]
               
                >1; ls=++tot; add(cr,ls); build(l,mid,ls); rs=++tot; add(cr,rs); build(mid+1,r,rs); } void qry(int l,int r,int cr,int L,int R,int k) { if(rk[a[l].l]>=L&&rk[a[r].l]<=R)// {vt[k].pb(cr);return;} if(l==r)return; int mid=l+r>>1;//return if(L<=rk[a[mid].l])qry(l,mid,ls,L,R,k); if(rk[a[mid+1].l]<=R)qry(mid+1,r,rs,L,R,k); } void dfs(int cr) { vis[cr]=ins[cr]=1; for(int i=hd[cr],v;i;i=nxt[i]) if(ins[v=to[i]]){flag=1;return;} else if(!vis[v]){dfs(v);if(flag)return;} ins[cr]=0; } void solve() { init(); for(int i=1;i<=na;i++)a[i].id=i; sort(a+1,a+na+1,cmp); tot=1; build(1,na,1); for(int i=1;i<=nb;i++) { Node d=cz(b[i].l,b[i].c); qry(1,na,1,d.l,d.r,i); } int m=rdn(),u,v; while(m--) { u=rdn();v=rdn(); for(int i=0,lm=vt[v].size();i
               
              
             
            
           
          
         
        
       
      

如果 |a|<|b| ，那么 b 在 sa 上对应的那个区间里不是所有的 a 都可以连边。

但如果把 a 按真实的字典序排序，那么 b 对应的 a 仍然是一段连续的区间。

按真实的字典序排序也很好做，只要作出后缀数组，然后查一下 LCP 看是不是大于两个串长度的较小值就行。（如果小于，就看不同字符；不然看长度谁短）

一个 b 可以在排序后的 a 上二分得到区间。合法区间需要满足 a[ ] >= b && LCP( a[ ] , b ) == b.len ；如果 a[ ] < b 就向右，如果 a[ ] >= b && LCP( a[ ] , b ) < b.len 就向左，这样就可以二分啦。

本地可过，交到洛谷上还是只有第 4 个点不 RE 。真是令人气急败坏！不管了。

交到 LOJ 上会除了第 4 个点之外全 WA 。但选择 C++(NOI) 提交的话就可过。不知为何。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define pb push_back#define ls Ls[cr]#define rs Rs[cr]using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
     return a>b?a:b;}ll Mn(ll a,ll b){
     return a
           

vt[N];queue

q;void Rsort(int n,int nm){ for(int i=1;i<=nm;i++)tx[i]=0; for(int i=1;i<=n;i++)tx[rk[i]]++; for(int i=2;i<=nm;i++)tx[i]+=tx[i-1]; for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i];}void get_sa(int n,int nm){ int mx=0,mn=N; for(int i=1;i<=n;i++) { rk[i]=s[i]-'a'+1,tp[i]=i; mx=Mx(mx,rk[i]); mn=Mn(mn,rk[i]); } Rsort(n,nm); for(int k=1;k<=n;k<<=1) { int tot=0; for(int i=n-k+1;i<=n;i++)tp[++tot]=i; for(int i=1;i<=n;i++) if(sa[i]>k)tp[++tot]=sa[i]-k; Rsort(n,nm); for(int i=1;i<=n;i++)tp[i]=rk[i]; rk[sa[1]]=nm=1; for(int i=2;i<=n;i++) { int u=sa[i]+k,v=sa[i-1]+k; if(u>n)u=0;if(v>n)v=0; rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm; } if(nm==n)break; }}void get_ht(int n){ for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; bin[0]=1; for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1; for(int i=1,k=0,j;i<=n;i++)//k=0 { for((k?k--:0),j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++); ht[rk[i]][0]=k; } for(int t=1;t<=lg[n];t++) for(int i=1;i+bin[t]-1<=n;i++) ht[i][t]=Mn(ht[i][t-1],ht[i+bin[t-1]][t-1]);}int qry_ht(int l,int r){ if(l==r)return n-sa[l]+1; if(l>r)swap(l,r); l++; int d=lg[r-l+1]; return Mn(ht[l][d],ht[r-bin[d]+1][d]);}struct Node{ int l,r,c,id; Node(int l=0,int r=0):l(l),r(r) {c=id=0;} bool operator< (const Node &b)const { int d=qry_ht(rk[l],rk[b.l]), len=Mn(c,b.c); if(d

>1; if(a[mid]

>1; if(a[mid]

>1; ls=++tot; add(cr,ls); build(l,mid,ls); rs=++tot; add(cr,rs); build(mid+1,r,rs);}void qry(int l,int r,int cr,int L,int R,int k){ if(l>=L&&r<=R){vt[k].pb(cr);return;} if(l==r)return; int mid=l+r>>1;//return if(L<=mid)qry(l,mid,ls,L,R,k); if(mid