codeforces 123 D. String （后缀数组+两次二分得到区间＋rmq）
题意：定义一个函数F．．
For exampe: _F_(_babbabbababbab_, _babb_) = 6. The list of pairs is as follows:(1, 4), (4, 7), (9, 12)
Its continuous sequences are:
*
(1, 4)
*
(4, 7)
*
(9, 12)
*
(1, 4), (4, 7)
*
(4, 7), (9, 12)
*
(1, 4), (4, 7), (9, 12)
erfen
． erfen 题目描述得很烂．．看例子把．．大概就是：如果字符串y在字符串x中出现n次，那么F(x,y)=n*(n+1)/2
现在给一个字符串，求所有的F(s,x)的和，x为字符串的所有不相同的子串．
思路：由于刚刚写了一个求一个字符串所有不同子串个数的题目．．．于是就想到了后缀数组．．．
写完之后观察height[i]．如果把height[i]看成底在x轴上的第i个矩形的高的话，n就是一段连续的矩形的长度．
然后．．．暴力会tle 48
题解说单调栈．．．但是单调栈之后还要线段树or并查集？ （by 羊神）
．．．不会啊orz
最后用了二分+rmp过掉的
大概就是两次二分得到一个矩形的区间，和whust2016 #1的那道题有点像．
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月01日 星期一 04时57分01秒
4File Name :code/cf/problem/123d.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#include <stack>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E5+7;
33int n,sa[N],rk[N],t[N],t2[N],cnt[N];
34int height[N];
35char s[N];
36int cmp( int *r , int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
37void getSa( int n,int m)
38{
39 int *x = t;
40 int *y = t2;
41 ms(cnt,0);
42 for ( int i = 0 ; i < n ; i++) cnt[x[i]=s[i]]++;
43 for ( int i = 1 ; i < m ; i++) cnt[i] +=cnt[i-1];
44 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i ;
45 for ( int k = 1 ; k <= n ; k <<=1)
46 {
47 int p = 0 ;
48 for ( int i = n-k ; i < n; i++) y[p++] = i;
49 for ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k;
50 ms(cnt,0);
51 for ( int i = 0 ; i <n ; i++) cnt[x[y[i]]]++;
52 for ( int i = 0 ; i < m ; i++) cnt[i] +=cnt[i-1];
53 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
54 swap(x,y);
55 p = 1;
56 x[sa[0]] = 0 ;
57 for ( int i = 1 ;i <n ; i++)
58 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
59 if (p>=n) break;
60 m = p;
61 }
62}
63void getHeight( int n)
64{
65 int k = 0 ;
66 for ( int i = 0 ; i < n ; i++) rk[sa[i]] = i ;
67 height[0] = 0 ;
68 for ( int i = 0 ; i < n ; i++)
69 {
70 if (rk[i]==0) continue;
71 if (k) k--;
72 int j = sa[rk[i]-1];
73 while (s[i+k]==s[j+k]) k++;
74 height[rk[i]] = k;
75 }
76}
77int getSuffix( char s[])
78{
79 int len = strlen(s);
80 int up = 0 ;
81 for ( int i = 0 ; i < len ; i++)
82 {
83 int val = s[i];
84 up = max(up,val);
85 }
86 s[len++]='$';
87 getSa(len,up+1);
88 getHeight(len);
89 return len;
90}
91LL cal( LL x)
92{
93 return x*(x+1)/2LL;
94}
95LL solve2(int n)
96{
97 for ( int i = 0 ; i < n ; i++) cout<<i<<" "<<height[i]<<endl;
98 ms(cnt,0);
99 int up = 0 ;
100 for ( int i = 1 ; i < n; i++) cnt[height[i]]++,up=max(up,height[i]);
101 for ( int i = up-1 ; i >= 0 ; i--) cnt[i] = cnt[i]+cnt[i+1];
102 LL res = 0LL ;
103 for ( int i = 0 ; i <= up ; i++)
104 res = res + cal(1LL*cnt[i]);
105 return res;
106}
107/*
108stack<int>stk;
109int l[N],r[N];
110bool visl[N],visr[N];
1LL solve ( LL n) //单调栈
2{
3 LL res = n*(n-1LL)/2LL;
4 int up = 0 ;abaabaabaaba
5 for ( int i = 1 ; i < n; i++) up = max(height[i],up);
6 // for ( int i = 1 ; i <= n ; i++) cout<<"i:"<<i<<" height[i]:"<<height[i]<<endl;
7 height[0] = -1;
8 height[n+1] = -1 ; //单调队列的哨兵
9 stk.push(0);
10 int x;
11 for ( int i = 1 ; i <= n; i++)
12 {
13 for (x=stk.top();height[x]>=height[i];x=stk.top()) stk.pop();
14 l[i] = x+1;
15 stk.push(i);
16// cout<<"i:"<<i<<endl;
17 }
18 while (!stk.empty()) stk.pop() ; stk.push(n+1);
19 for ( int i = n ; i >=1 ; i--)
20 {
21 for (x=stk.top() ; height[x]>=height[i] ; x = stk.top()) stk.pop();
22 r[i] = x-1;
23 stk.push(i);
24 }
25 // for ( int i = 1 ; i <= n ; i++)
26// cout<<"i:"<<i<<" l[i]:"<<l[i]<<" r[i]:"<<r[i]<<" height[i]:"<<height[i]<<" "<<(r[i]-l[i]+1)*height[i]<<endl;
27// int mxh = 0 ;
28 ms(visl,false);
29 ms(visr,false);
30 int mxh = 0 ;
31 int more =1;
32 for ( int i = 1 ;i <= n ; i++)
33 {
34 if (height[i]==0)
35 {
36 mxh = 0 ;
37 continue;
38 }
39 if (visr[r[i]]&&visl[l[i]])
40 {
41 mxh = 0 ;
42 continue;
43 }
44 if (i>1&&height[i-1]<height[i]) more = height[i]-height[i-1];
45 if (i<n&&height[i+1]<height[i]) more = min(more,height[i]-height[i+1]);
46 res = res + cal((r[i]-l[i]+1))*(more);
47 mxh = max(mxh,height[i]);
48 visr[r[i]] = true;
49 visl[l[i]] = true;
50// cout<<"i:"<<i<<" res:"<<res<<endl;
}
return res;
} */
1int dp[N][30]; // for rmq;
2void rmq_init( int n)
3{
4 for ( int i = 1 ; i <= n ; i++) dp[i][0] = height[i];
1 for ( int j = 1 ; (1<<j) <= n ; j++)
2 for ( int i = 1 ; i + (1<<j) - 1 <= n ; i++)
3 dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
4}
5int rmq( int l,int r)
6{
7 if (l>r) swap(l,r);
8 int k = 0 ;
9 while (1<<(k+1)<=r-l+1) k++;
10 int res = min(dp[l][k],dp[r-(1<<k)+1][k]);
11 return res;
}
1LL solve( LL len)
2{
3 rmq_init(len);
4 LL ans = len*(len+1)/2;
1 // for ( int i = 1 ; i <= len ; i++) cout<<i<<" :"<<height[i]<<endl;
2 for ( int i = 1 ; i <= len ; i++)
3 {
4 int l = 0 ,r = i ;
5 while (r>l+1)
6 {
7 int mid = (l+r)/2;
8 if (rmq(mid,i-1)>=height[i]) r = mid;
9 else l = mid;
10 }
11 int L = i,R= len+1;
12 while (R>L+1)
13 {
14 int mid = (L+R) / 2;
15 if (rmq(i+1,mid)>height[i]) L = mid;
16 else R = mid;
17 }
18// cout<<"i:"<<height[i]<<"L:"<<L<<" r:"<<r<<" ans:"<<ans<<endl;
19 ans +=1LL*height[i]*(L-i+1)*(i-r+1);
20 }
21 return ans;
22}
23int main()
24{
25 #ifndef ONLINE_JUDGE
26 freopen("code/in.txt","r",stdin);
27 #endif
28 scanf("%s",s);
29 int len = getSuffix(s);
30// cout<<"len:"<<len-1<<endl;
31 LL ans = solve(len-1);
32 printf("%lld\n",ans);
33 #ifndef ONLINE_JUDGE
34 fclose(stdin);
35 #endif
36 return 0;
37}