题解:后缀数组的特性我们可以通过对于这个位置比较前一个位置的h值来解决以i位置为起点的后缀能产生多少个和前面的串不同的子串 所以问题转化为 求第k大出现的位置 二分找就ok 然后找出来的位置求一下lcp 然后反过来再求一下就ok

#include 
     
      #define ll long longconst int MAXN=1e5+10;using namespace std;char s1[MAXN],s2[MAXN];int txt[MAXN],sa[MAXN],td[MAXN],rank1[MAXN],rank2[MAXN],t1[MAXN],t2[MAXN];int dp[MAXN][21];int mu[21];int ma[MAXN];bool cmp(int f[],int t,int w,int k){return f[t]==f[w]&&f[t+k]==f[w+k];}ll ans[MAXN];void Sa(char str[]){  //  cout<
      
       <
       
        =0;i--)sa[--txt[str[i]]]=i;    for(int k=1;k<=len;k=k*2){	int p=0;	for(int i=len-k;i
        
         =k)td[p++]=sa[i]-k;	for(int i=0;i
         
          =0;i--)sa[--txt[rank1[td[i]]]]=td[i];	swap(rank1,td);rank1[sa[0]]=0;p=1;	for(int i=1;i
          
           r)return MAXN; int k=ma[r-l+1]; return min(dp[l][k],dp[r-mu[k]+1][k]);}typedef struct node{ ll l,r;int lx,rx,ly,ry;}node;node que[MAXN];int q;int check(ll k,int len){ int l=1;int r=len-1; while(l<=r){ int mid=(l+r)>>1; if(sum[mid-1]
           
            =k)return mid; else if(sum[mid-1]>=k)r=mid-1; else l=mid+1; } return len;}void slove(){ Sa(s1);hh(s1);int len=strlen(s1);st(len); // cout<
            
             <<" "<
             
              =len||que[i].ly>=len){ ans[i]=-1;continue; } que[i].rx=que[i].l-sum[que[i].lx-1]+h[que[i].lx];que[i].ry=que[i].r-sum[que[i].ly-1]+h[que[i].ly];// cout<
              
               <<"----"<
               
                <
                
                 r)swap(l,r);l++; ll k1=1ll*min(que[i].lx,min(que[i].ly,rmq(l,r))); ans[i]+=1ll*k1*k1; }}int main(){ mu[0]=1;for(int i=1;i<=20;i++)mu[i]=mu[i-1]<<1; ma[0]=-1;for(int i=1;i
                
               
              
             
            
           
          
         
        
       
      
     

 

3230: 相似子串

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1980  Solved: 515

[][][]

Description

Input

输入第1行，包含3个整数N，Q。Q代表询问组数。

第2行是字符串S。

接下来Q行，每行两个整数i和j。（1≤i≤j）。

Output

输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。

Sample Input

5 3

ababa

3 5

5 9

8 10

Sample Output

18

16

-1

HINT

样例解释

第1组询问：两个子串是“aba”,“ababa”。f = 32 + 32 = 18。

第2组询问：两个子串是“ababa”,“baba”。f = 02 + 42 = 16。

第3组询问：不存在第10个子串。输出-1。

 

数据范围

N≤100000，Q≤100000，字符串只由小写字母'a'~'z'组成