BZOJ 3238: [Ahoi2013]差异( 后缀数组 + 单调栈 )

sa后求出height数组, 答案显然是∑RMQ(height[l],height[r])(1≤l<r≤N), 然后单调栈乱搞O(N)解决. 写了一个晚上, 再这样下去我就得退役了, 呵呵..

----------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<stack>

 

using namespace std;

 

typedef long long ll;

 

#define b(i) (1 << (i))

 

const int maxn = 500009;

const int maxlog = 22;

 

char S[maxn];

int sa[maxn], height[maxn], rank[maxn], cnt[maxn], L[maxn], R[maxn], N;

stack<int> sta;

 

void build() {

int m = 27, *x = height, *y = rank;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[i] = S[i]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N; i--; ) sa[--cnt[x[i]]] = i;

for(int k = 1; k <= N; k <<= 1) {

int p = 0;

for(int i = N - k; i < N; i++) y[p++] = i;

for(int i = 0; i < N; i++) if(sa[i] >= k) y[p++] = sa[i] - k;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[y[i]]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N; i--; ) sa[--cnt[x[y[i]]]] = y[i];

swap(x, y); x[sa[0]] = 0; p = 1;

for(int i = 1; i < N; i++)

x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p-1 : p++;

if(p >= N) break;

m = p;

}

for(int i = 0; i < N; i++) rank[sa[i]] = i;

int k = 0;

for(int i = 0; i < N; i++) {

if(k) k--;

while(S[i + k] == S[sa[rank[i] - 1] + k]) k++;

height[rank[i]] = k;

}

}

 

void init() {

scanf("%s", S);

N = strlen(S);

for(int i = 0; i < N; i++) S[i] = S[i] - 'a' + 1;

S[N++] = 0;

}

 

void work() {

ll ans = ll(N) * (N - 1) * (N - 2) / 2;

sta.push(L[1] = 1);

for(int i = 2; i < N; i++) {

while(!sta.empty() && height[sta.top()] >= height[i]) sta.pop();

L[i] = sta.empty() ? 1 : sta.top() + 1;

sta.push(i);

}

while(!sta.empty()) sta.pop();

sta.push(R[N - 1] = N - 1);

for(int i = N - 2; i; i--) {

while(!sta.empty() && height[sta.top()] > height[i]) sta.pop();

R[i] = sta.empty() ? N - 1 : sta.top() - 1;

sta.push(i);

}

for(int i = 1; i < N; i++)

   ans -= ll(height[i]) * (R[i] - i + 1) * (i - L[i] + 1) << 1;

printf("%lld ", ans);

}

 

int main() {

init();

build();

work();

return 0;

}

----------------------------------------------------------------

3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1117  Solved: 532
[Submit][Status][Discuss]

Description

Input

一行，一个字符串S

Output

 

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

Source