[Ahoi2013]差异

　　后缀数组+单调栈

　　代码

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N = ;

 const int MAXN =  N;

 struct SuffixArray{

     int wa[MAXN];

     int wb[MAXN];

     int wv[MAXN];

     int ws[MAXN];

     int sa[MAXN];

     int rank[MAXN];

     int height[MAXN];

     int r[MAXN];

     int n;

     int m;

     void input(int *val, int len, int Max){

         for (int i = ;i < len;i++)

             r[i] = val[i];

         r[len] = ;

         n = len;

         m = Max;

         calSa();

         calHeight();

     }

     int cmp(int *r, int a, int b, int l){

         return (r[a] == r[b] && r[a + l] == r[b + l]);

     }

     void calSa(){

         int i, j, p, *x = wa, *y = wb, *t;

         for (i = ;i < m;i++) ws[i] = ;

         for (i = ;i < n + ;i++) ws[x[i] = r[i]]++;

         for (i = ;i < m;i++) ws[i] += ws[i - ];

         for (i = n;i >= ;i--) sa[--ws[x[i]]] = i;

         for (j = , p = ;p < n + ;j *= , m = p){

             for (p = , i = n - j + ;i < n + ;i++) y[p++] = i;

             for (i = ;i < n + ;i++) if (sa[i] >= j) y[p++] = sa[i] - j;

             for (i = ;i < n + ;i++) wv[i] = x[y[i]];

             for (i = ;i < m;i++) ws[i] = ;

             for (i = ;i < n + ;i++) ws[wv[i]]++;

             for (i = ;i < m;i++) ws[i] += ws[i - ];

             for (i = n;i >= ;i--) sa[--ws[wv[i]]] = y[i];

             for (t = x, x = y, y = t, p = , x[sa[]] = , i = ; i < n + ;i++)

                 x[sa[i]] = cmp(y, sa[i - ], sa[i], j) ? p -  : p++;

         }

     }

     void calHeight(){

         int i, j, k = ;

         for (i = ;i <= n;i++) rank[sa[i]] = i;

         for (i = ;i < n;height[rank[i++]] = k)

             for (k?k--:, j = sa[rank[i]- ];r[i + k] == r[j + k];k++);

     }

     int Log[MAXN];

     int best[][MAXN];

     void initRMQ() {

         Log[] = -;

         for(int i = ;i <= MAXN;i++){

             Log[i]=(i & (i - ))?Log[i - ] : Log[i - ] +  ;

         }

         for(int i = ; i <= n ; i ++) best[][i] = height[i];

         for(int i = ; i <= Log[n] ; i ++) {

             int limit = n - (<<i) + ;

             for(int j = ; j <= limit ; j ++) {

                 best[i][j] = (best[i-][j] > best[i-][j+(<<i>>)]) ? best[i-][j+(<<i>>)] : best[i-][j];

             }

         }

     }

     int lcp(int a,int b) {

         a = rank[a];    b = rank[b];

         if(a > b){

             int t = a;

             a = b;

             b = t;

         }

         a ++;

         int t = Log[b - a + ];

         return (best[t][a] > best[t][b - (<<t) + ])? best[t][b - (<<t) + ] : best[t][a];

     }

 }SA;

 int a[N],i,len,top,stack[N];

 long long ans,sum;

 char s[N];

 int main()

 {

     scanf("%s",&s);

     len=strlen(s);

     for (i=;i<=len;i++)

     {

         ans=ans+(long long)i*(len-);

         a[i-]=s[i-];

     }

     SA.input(a,len,);

     for (i=;i<=len;i++)

     {

         while (SA.height[i]<SA.height[stack[top]])

         {

             sum=sum-(long long)(stack[top]-stack[top-])*SA.height[stack[top]];

             top--;

         }

         top++;stack[top]=i;

         sum=sum+(long long)(stack[top]-stack[top-])*SA.height[stack[top]];

         ans=ans-*sum;

     }

     printf("%lld\n",ans);

 }

 //3 1 4 2 5 0