题意：定义一个函数 F。
For example: 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)
二分。
题目描述得很烂，看例子吧，大概就是：如果字符串 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
最后用了二分 + rmq 过掉的
大概就是两次二分得到一个矩形的区间，和 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];
111
112LL solve ( LL n) //单调栈
113{
114 LL res = n*(n-1LL)/2LL;
115 int up = 0 ;abaabaabaaba
116 for ( int i = 1 ; i < n; i++) up = max(height[i],up);
117 // for ( int i = 1 ; i <= n ; i++) cout<<"i:"<<i<<" height[i]:"<<height[i]<<endl;
118 height[0] = -1;
119 height[n+1] = -1 ; //单调队列的哨兵
120 stk.push(0);
121 int x;
122 for ( int i = 1 ; i <= n; i++)
123 {
124 for (x=stk.top();height[x]>=height[i];x=stk.top()) stk.pop();
125 l[i] = x+1;
126 stk.push(i);
127// cout<<"i:"<<i<<endl;
128 }
129 while (!stk.empty()) stk.pop() ; stk.push(n+1);
130 for ( int i = n ; i >=1 ; i--)
131 {
132 for (x=stk.top() ; height[x]>=height[i] ; x = stk.top()) stk.pop();
133 r[i] = x-1;
134 stk.push(i);
135 }
136 // for ( int i = 1 ; i <= n ; i++)
137// cout<<"i:"<<i<<" l[i]:"<<l[i]<<" r[i]:"<<r[i]<<" height[i]:"<<height[i]<<" "<<(r[i]-l[i]+1)*height[i]<<endl;
138// int mxh = 0 ;
139 ms(visl,false);
140 ms(visr,false);
141 int mxh = 0 ;
142 int more =1;
143 for ( int i = 1 ;i <= n ; i++)
144 {
145 if (height[i]==0)
146 {
147 mxh = 0 ;
148 continue;
149 }
150 if (visr[r[i]]&&visl[l[i]])
151 {
152 mxh = 0 ;
153 continue;
154 }
155 if (i>1&&height[i-1]<height[i]) more = height[i]-height[i-1];
156 if (i<n&&height[i+1]<height[i]) more = min(more,height[i]-height[i+1]);
157 res = res + cal((r[i]-l[i]+1))*(more);
158 mxh = max(mxh,height[i]);
159 visr[r[i]] = true;
160 visl[l[i]] = true;
161// cout<<"i:"<<i<<" res:"<<res<<endl;
162
163 }
164
165 return res;
166} */
167
168int dp[N][30]; // for rmq;
169void rmq_init( int n)
170{
171 for ( int i = 1 ; i <= n ; i++) dp[i][0] = height[i];
172
173 for ( int j = 1 ; (1<<j) <= n ; j++)
174 for ( int i = 1 ; i + (1<<j) - 1 <= n ; i++)
175 dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
176}
177int rmq( int l,int r)
178{
179 if (l>r) swap(l,r);
180 int k = 0 ;
181 while (1<<(k+1)<=r-l+1) k++;
182 int res = min(dp[l][k],dp[r-(1<<k)+1][k]);
183 return res;
184
185}
186
187LL solve( LL len)
188{
189 rmq_init(len);
190 LL ans = len*(len+1)/2;
191
192 // for ( int i = 1 ; i <= len ; i++) cout<<i<<" :"<<height[i]<<endl;
193 for ( int i = 1 ; i <= len ; i++)
194 {
195 int l = 0 ,r = i ;
196 while (r>l+1)
197 {
198 int mid = (l+r)/2;
199 if (rmq(mid,i-1)>=height[i]) r = mid;
200 else l = mid;
201 }
202 int L = i,R= len+1;
203 while (R>L+1)
204 {
205 int mid = (L+R) / 2;
206 if (rmq(i+1,mid)>height[i]) L = mid;
207 else R = mid;
208 }
209// cout<<"i:"<<height[i]<<"L:"<<L<<" r:"<<r<<" ans:"<<ans<<endl;
210 ans +=1LL*height[i]*(L-i+1)*(i-r+1);
211 }
212 return ans;
213}
214int main()
215{
216 #ifndef ONLINE_JUDGE
217 freopen("code/in.txt","r",stdin);
218 #endif
219 scanf("%s",s);
220 int len = getSuffix(s);
221// cout<<"len:"<<len-1<<endl;
222 LL ans = solve(len-1);
223 printf("%lld\n",ans);
224 #ifndef ONLINE_JUDGE
225 fclose(stdin);
226 #endif
227 return 0;
228}