令${str\left(i,j \right)}$为区间${[l,r]}$所表示的子串。

对于任意$r$

一,求${\sum _{i=1}^{n}\sum _{j=i+1}^{n}[str(i,i+r-1)=str(j,j+r-1)]}$

二,求${ans[r]=max(val[i]*val[j])}$,且${str(i,i+r-1)=str(j,j+r-1)}$

---

　　直接用SAM构出后缀树，然后一个子串一定是原串的一个后缀的前缀，然后找到后缀树中每一个后缀对应的节点，每一对后缀的LCP对应了后缀树中的相应点的LCA的len(即代表的最长串的长度)，然后做一遍树形统计统计第一问答案，第二问答案即要记一下子树最大值最小值即可。

---

　　

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 1000100 10 #define llg long long 11 #define SIZE 26 12 #define inf (((llg)1e18)+10) 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 llg n,m,ans1[maxn<<1],ans2[maxn<<1],val[maxn],zhu[maxn<<1],quan[maxn<<1],tail; 15 llg minl[maxn<<1],maxl[maxn<<1],ans3[maxn<<1]; 16 char s[maxn]; 17 18 struct SAM 19 { 20 struct 21 { 22 llg len,f,ch[SIZE]; 23 void init() 24 { 25 len=0,f=-1; 26 memset(ch,0xff,sizeof(ch)); 27 } 28 }e[maxn<<1]; 29 30 vector
            
             a[maxn<<1]; 31 llg idx,last,size[maxn<<1]; 32 33 void init(){idx=last=0; e[idx++].init(); memset(size,0,sizeof(size)); } 34 35 llg newnode(){e[idx].init(); return idx++;} 36 37 void insert(llg c) 38 { 39 llg end=newnode(),tmp=last; 40 e[end].len=e[last].len+1; size[end]=1; zhu[end]=1; quan[end]=val[tail]; maxl[end]=val[tail],minl[end]=val[tail]; tail++; 41 for (;tmp!=-1 && e[tmp].ch[c]==-1;tmp=e[tmp].f) 42 e[tmp].ch[c]=end; 43 if (tmp==-1) e[end].f=0; 44 else 45 { 46 llg nxt=e[tmp].ch[c]; 47 if (e[tmp].len+1==e[nxt].len) e[end].f=nxt; 48 else 49 { 50 llg np=newnode();// maxl[np]=maxl[end],minl[np]=minl[end]; 51 e[np]=e[nxt]; 52 e[np].len=e[tmp].len+1; 53 e[nxt].f=e[end].f=np; 54 for (;tmp!=-1 && e[tmp].ch[c]==nxt;tmp=e[tmp].f) {e[tmp].ch[c]=np;} 55 } 56 } 57 last=end; 58 // cout<
             
              <
              
               >n; 94 sam.init(); 95 scanf("%s",s); 96 for (llg i=0;i<=n*2;i++) ans2[i]=maxl[i]=-1*inf,minl[i]=inf,ans3[i]=inf*-1; 97 for (llg i=0;i
               
                =0;i--) 100 sam.insert(s[i]-'a');101 sam.link_fa();102 sam.dp(0);103 for (llg i=n-1;i>=1;i--) 104 {105 ans1[i-1]+=ans1[i];106 if (ans1[i]) ans2[i-1]=max(ans2[i-1],ans2[i]);107 }108 // for (llg i=0;i