# bzoj3238 差异(后缀数组+单调栈)(Bzoj3238 difference (suffix array + monotone stack))-其他

## bzoj3238 差异(后缀数组+单调栈)(Bzoj3238 difference (suffix array + monotone stack))

### 代码

``````const int maxn = 1e6+10;
int n, m;
char s[maxn];
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], h[maxn];
void get_sa() {
for (int i = 1; i<=n; ++i) ++c[x[i]=s[i]];
for (int i = 2; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[i]]--] = i;
for (int k = 1; k<=n; k<<=1) {
int num = 0;
for (int i = n-k+1; i<=n; ++i) y[++num] = i;
for (int i = 1; i<=n; ++i)
if (sa[i]>k) y[++num] = sa[i]-k;
for (int i = 1; i<=m; ++i) c[i] = 0;
for (int i = 1; i<=n; ++i) ++c[x[i]];
for (int i = 1; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int i = 2; i<=n; ++i)
x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
if (num==n) break;
m = num;
}
}
void get_h() {
for (int i = 1; i<=n; ++i) rk[sa[i]] = i;
for (int i = 1, k = 0; i<=n; ++i) {
if (rk[i]==1) continue;
if (k) --k;
int j = sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) ++k;
h[rk[i]] = k;
}
}
stack<int> sk;
int l[maxn]; ll lcp[maxn];
int main() {
IOS;
cin >> s+1;
n = strlen(s+1); m = 122;
get_sa(); get_h();
h[0] = -1;
for (int i = n; i>=0; --i) {
while(!sk.empty() && h[sk.top()]>h[i]) {
l[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
ll sum = 0;
for (int i = 1; i<=n; ++i) {
lcp[i] = lcp[l[i]]+2LL*(i-l[i])*h[i];
sum += 1LL*(n-1)*(n-i+1)-lcp[i];
}
cout << sum << endl;
return 0;
}
``````
————————

### Problem solving ideas

The front part can be solved directly. The key is how to quickly solve the second half.
We know the LCP between the two suffixes, that is, the minimum value of the height array between them. Since the topic is to count different pairs of numbers, we can reorder the suffixes according to rk. Each time we calculate the LCP of the current suffix J and the suffix I in front of it, it is not difficult to find that the minimum value obtained by taking min for height in the process from J to I is piece by piece.
We can use the monotone stack to calculate the minimum left endpoint l [J] that can be extended to each block with the current subscript j as the right endpoint and height [J] as the minimum value of the interval, and then use the idea of DP to deduce the sum of the current suffix and the LCP of the suffix in front of him according to l [J].

### code

``````const int maxn = 1e6+10;
int n, m;
char s[maxn];
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], h[maxn];
void get_sa() {
for (int i = 1; i<=n; ++i) ++c[x[i]=s[i]];
for (int i = 2; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[i]]--] = i;
for (int k = 1; k<=n; k<<=1) {
int num = 0;
for (int i = n-k+1; i<=n; ++i) y[++num] = i;
for (int i = 1; i<=n; ++i)
if (sa[i]>k) y[++num] = sa[i]-k;
for (int i = 1; i<=m; ++i) c[i] = 0;
for (int i = 1; i<=n; ++i) ++c[x[i]];
for (int i = 1; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int i = 2; i<=n; ++i)
x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
if (num==n) break;
m = num;
}
}
void get_h() {
for (int i = 1; i<=n; ++i) rk[sa[i]] = i;
for (int i = 1, k = 0; i<=n; ++i) {
if (rk[i]==1) continue;
if (k) --k;
int j = sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) ++k;
h[rk[i]] = k;
}
}
stack<int> sk;
int l[maxn]; ll lcp[maxn];
int main() {
IOS;
cin >> s+1;
n = strlen(s+1); m = 122;
get_sa(); get_h();
h[0] = -1;
for (int i = n; i>=0; --i) {
while(!sk.empty() && h[sk.top()]>h[i]) {
l[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
ll sum = 0;
for (int i = 1; i<=n; ++i) {
lcp[i] = lcp[l[i]]+2LL*(i-l[i])*h[i];
sum += 1LL*(n-1)*(n-i+1)-lcp[i];
}
cout << sum << endl;
return 0;
}
``````