1 #include
     
        2 #include
      
         3 typedef __int64 LL;  4 #define MAXN 200010  5 char s[MAXN];  6 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];  7 int sa[MAXN],height[MAXN],rk[MAXN];  8 int stk[MAXN],cnt[MAXN];  9 inline bool cmp(int *r,int a,int b,int len) 10 { 11     return r[a]==r[b]&&r[a+len]==r[b+len]; 12 } 13 void SA(int n,int m) 14 { 15     int i,j,p,*x=wa,*y=wb,*t; 16     for(i=0;i
       
        =0;i--) 23         sa[--ws[x[i]]]=i; 24     for(j=p=1;p
        
         <<=1,m=p) 25     { 26         for(p=0,i=n-j;i
         
          =j) 31                 y[p++]=sa[i]-j; 32         } 33         for(i=0;i
          
           =0;i--) 40 sa[--ws[wv[i]]]=y[i]; 41 for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i
           
            =k) 69 height[i]-=k-1; 70 else 71 height[i]=0; 72 } 73 ans=temp=0; 74 top=-1; 75 for(i=1;i<=n;i++) 76 { 77 for(size=0;top>-1&&stk[top]>height[i];top--) 78 { 79 size+=cnt[top]; 80 temp+=(height[i]-stk[top])*cnt[top]; 81 } 82 stk[++top]=height[i]; 83 cnt[top]=size; 84 if(sa[i-1]
            
             len) 90 ans+=temp; 91 } 92 temp=0; 93 top=-1; 94 for(i=1;i<=n;i++) 95 { 96 for(size=0;top>-1&&stk[top]>height[i];top--) 97 { 98 size+=cnt[top]; 99 temp+=(height[i]-stk[top])*cnt[top];100 }101 stk[++top]=height[i];102 cnt[top]=size;103 if(sa[i-1]>len)104 {105 temp+=height[i];106 cnt[top]++;107 }108 if(sa[i]