0 说在之前

jt 学长说的没错，SA 果然是写一次忘一次……

于是这次重新学了一次，发现之前的 Blog 问题比较多，于是重写一次算了

实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页，不过是写给自己的罢了

1 什么是后缀数组

1.0 一些约定

• 字符串下标从 1 开始
• $s[ x \dots y ]$ 表示从 s[x] 到 s[y] 的连续子串
• $s[ x \dots ]$ 表示从 s[x] 到字符串结尾的连续子串
• $s[x \dots y ] = t[ a \dots b ]$ 表示这两个子串的每一位都相同

1.1 后缀数组的定义

后缀数组，即 SA(Suffix Array)

后缀数组通常是两个数组，sa[] 和 rank[]

sa[i] 表示第 $i$ 名的后缀开始位置

rank[i] 表示从 $i$ 开始的后缀的排名

也就是 rank[ sa[i] ] = i

1.2 倍增求法

后缀数组最暴力的求法应该是 $O(n^2\log(n))$，但是这个显然太慢了……

后缀数组常见的比这个快的有两种 $O(n)$ 的求法，和 $O(n\log(n))$ 的倍增法

鉴于我确实还没有见到过 $O(n)$ 求后缀数组的题目（实际上是有的，但是我都不会）

所以本篇博客还是只写倍增求后缀数组

1.2.1 倍增什么

注意到每个后缀之间是有包含关系的。所以我们可以将长度为 $k$ 的字符串看作一个数字，即其现在的排名

然后就可以快速的求出 $2k$ 的字符串排名（即双关键字排序）

使用快速排序的话就是 $O(n\log^2(n))$

使用基数排序的话就是 $O(n\log(n))$

1.2.2 优化常数

1. 注意到基数排序的桶大小是不断变化的，所以我们可以在每次倍增的时候更改桶的大小
2. 没有必要给第二关键字跑基数排序。由于我们已经有了在 $k$ 长度下确定的顺序，所以可以按照顺序添加第一关键字，即完成了对第二关键字的排序

2 height 数组

2.0 LCP 最长公共前缀

两个字符串 $S$ 和 $T$ 的 LCP 是最长的 满足
$S[ 1 \dots x ] = T[ 1 \dots x ]( 1 \leq x \leq \min( |S|, |T| ) )$
的子串

定义 $lcp(i,j)$ 表示两个后缀的 LCP 长度

2.1 height 数组的定义

$$height_i = lcp( sa_i, sa_{i-1})$$

2.2 利用 SA O(n) 求后缀数组

2.2.1 一个引理

height[ rank[i] ] <= height[ rank[ i - 1 ] ] - 1

(为什么不用 $\LaTeX$ 公式？对于这种数组套数组的，个人认为还是用 <code> 括起来容易看懂……）

证明请查阅 https://oi-wiki.org/string/sa/#on-height

2.2.2 代码

for( int i = 1, k = 0; i <= len; i ++ ) {
    if( k ) 
        k --;
    while( str[ i + k ] == str[ sa[ rk[i] - 1 ] + k ] ) 
        k ++;
    height[ rk[i] ] = k;
}

2.3 利用 height 数组求 LCP

$$lcp( sa_i, sa_j ) = \min\{height_x\}( i + 1 \leq x \leq j )$$

3 LOJ 2133

3.1 思路

先简化题意，题目要求我们求求两个东西

1. $lcp(i,j)$ 大于等于 r（记为集合 $\bf{R}$）的个数
2. 在 $\bf{R}$ 中，val[i] * val[j] 的最大值

考虑 height 数组表示了相邻后缀的 LCP，和通过 height 数组求 LCP 的方法

对 height 数组排序后，按秩合并即可

3.2 代码

#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T a, T b ) { return a < b? a: b; }
template<class T>
T Max( T a, T b ) { return a > b? a: b; }

const int N = 3e5 + 1e4;
const long long INF = ( 1LL << 62LL );

int n;
char S[N];
int val[N];
int min[N], max[N], size[N], id[N];
long long cnt[N], res[N], ans[N];

struct set {
    int fa[N];
    inline void init( int n ) {
        for( int i = 0; i <= n; i ++ ) {
            fa[i] = i;
        }
    }
    int get_fa( int cur ) {
        if( fa[cur] == cur ) 
            return cur;
        return fa[cur] = get_fa( fa[cur] );
    }
    int &operator[] ( int cur ) { return fa[cur]; }
} fa;

void merge( int x, int y, int len ) {
    x = fa.get_fa(x); y = fa.get_fa(y);
    fa[y] = x;
    cnt[len] += 1LL * size[x] * size[y];
    size[x] += size[y];
    res[x] = Max( Max( res[x], res[y] ), 
            Max( Max( 1LL * max[x] * max[y], 1LL * min[x] * min[y] ), 
                Max( 1LL * max[x] * min[y], 1LL * min[x] * max[y] ) ) );
    min[x] = Min( min[x], min[y] );
    max[x] = Max( max[x], max[y] );
    ans[len] = Max( ans[len], res[x] );
}

struct suffix_array {
    int len, Max_char;
    int height[N], sa[N], rk[N], tp[N];
    char *str;
    // Init
    void sort() {
        static int rk_cnt[N];
        memset( rk_cnt, 0, sizeof(rk_cnt) );
        for( int i = 1; i <= len; i ++ ) 
            rk_cnt[ rk[i] ] ++;
        for( int i = 1; i <= Max_char; i ++ ) 
            rk_cnt[i] += rk_cnt[ i - 1 ];
        for( int i = len; i >= 1; i --  )
            sa[ rk_cnt[ rk[ tp[i] ] ] -- ] = tp[i];
    }
    void init( char *S, int _len ) {
        str = S;
        len = _len;
        Max_char = 'z' - 'a' + 2;
        for( int i = 1; i <= len; i ++ ) {
            rk[i] = str[i] - 'a' + 1;
            tp[i] = i;
        }
        sort();

        for( int k = 1, tmp_cnt = 0; tmp_cnt < len; k <<= 1, Max_char = tmp_cnt ) {
            tmp_cnt = 0;
            for( int i = 1; i <= k; i ++ ) {
                tp[ ++ tmp_cnt ] = len - k + i;
            }
            for( int i = 1; i <= len; i ++ ) {
                if( sa[i] > k ) 
                    tp[ ++ tmp_cnt ] = sa[i] - k;
            }
            sort();

            memcpy( tp, rk, sizeof(rk) );
            rk[ sa[1] ] = tmp_cnt = 1;
            for( int i = 2; i <= len; i ++ ) {
                if( tp[ sa[i] ] == tp[ sa[ i - 1 ] ] && tp[ sa[i] + k ] == tp[ sa[ i - 1 ] + k ] )
                    rk[ sa[i] ] = tmp_cnt;
                else {
                    tmp_cnt ++;
                    rk[ sa[i] ] = tmp_cnt;
                }
            }
        }
#ifdef woshiluo
        for( int i = 1; i <= n; i ++ ) printf( "%d ", sa[i] );
        printf( "\n" );
#endif
    }
    void get_height() {
        for( int i = 1, k = 0; i <= len; i ++ ) {
            if( k ) 
                k --;
            while( str[ i + k ] == str[ sa[ rk[i] - 1 ] + k ] ) 
                k ++;
            height[ rk[i] ] = k;
        }
    }
} sa;

bool cmp( int a, int b ) { return sa.height[a] > sa.height[b]; }

int main() {
#ifdef woshiluo
    freopen( "loj.2133.in", "r", stdin );
    freopen( "loj.2133.out", "w", stdout );
#endif
    scanf( "%d", &n );
    scanf( "%s", S + 1 );

    sa.init( S, n );
    sa.get_height();

    fa.init(n);
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%d", &val[i] );
        size[i] = 1; min[i] = max[i] = val[i]; res[i] = ans[i] = -INF;
        id[i] = i;
    }
    ans[ n + 1 ] = -INF;

    std::sort( id + 2, id + n + 1, cmp );

    for( int i = 2; i <= n; i ++ ) {
        merge( sa.sa[ id[i] ], sa.sa[ id[i] - 1 ], sa.height[ id[i] ] );
    }

    for( int i = n; i >= 0; i --  ) 
        cnt[i] += cnt[ i + 1 ];
    for( int i = n; i >= 0; i -- )
        ans[i] = Max( ans[i], ans[ i + 1 ] );
    for( int i = 0; i < n; i ++ ) {
        printf( "%lld %lld\n", cnt[i], cnt[i] == 0? 0: ans[i] );
    }
}