【NOI2015】品酒大会

题目链接，同步赛的时候不会 SA , 所以当时不会做这个题2333

如果我们想要求出长度为 r 的相同子串的对数

将满足 height[i]≥r 的 i 的集合与 i−1 的集合合并

那么每个集合内的子串都是 “ r 相似” 的

cnt[r] 表示 height[i]=r 时的方案数

max[r] 表示 height[i]=r 时的最大值

那么，按 height 值从大到小将集合合并,

合并时, 记 x ，y 为要合并的两个集合，那么

cnt[r] += size[x]*size[y]

ans[r] = max{max[x]*max[y] , min[x]*min[y]}

最后从大到小计算答案

cnt ′ [r] += cnt′[r + 1] + cnt[r]

ans ′ [r] = max{ans′[r + 1],ans[r]}

时间复杂度: O(N∗logN)

// savour uoj#131

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
    char c; int flag = ;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<) + (x<<) + (c-'0');
    x *= flag;
    return;
}
template<class Num>void write(Num x)
{
    if(x < ) putchar('-'), x = -x;
    static char s[];int sl = ;
    while(x) s[sl++] = x% + '0',x /= ;
    if(!sl) {putchar('0');return;}
    while(sl) putchar(s[--sl]);
}

const int maxn =  + ;

char s[maxn];

int a[maxn];

int n, sa[maxn], rank[maxn];
int c[maxn], height[maxn];

int fa[maxn], size[maxn];
long long max[maxn], min[maxn];

long long cnt, ans;
long long outc[maxn], outa[maxn];

struct Edge
{
    int v, next;

    Edge(int v = ,int next = ):v(v), next(next){}

}edge[maxn];
int head[maxn], el;

int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void newedge(int u,int v)
{
    edge[++el] = Edge(v, head[u]), head[u] = el;
}
void build_sa(int m)
{
    static int t0[maxn], t1[maxn];
    int *x = t0, *y = t1;

    for(int i = ; i <= m; i++) c[i] = ;
    for(int i = ; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = ; i <= m; i++) c[i] += c[i - ];
    for(int i = n; i >= ; i--) sa[c[x[i]]--] = i;

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

        for(int i = ; i <= m; i++) c[i] = ;
        for(int i = ; i <= n; i++) c[x[y[i]]]++;
        for(int i = ; i <= m; i++) c[i] += c[i - ];
        for(int i = n; i >= ; i--) sa[c[x[y[i]]]--] = y[i];

        std::swap(x, y);

        x[sa[p = ]] = ;

        for(int i = ; i <= n; i++)
            x[sa[i]] = y[sa[i]] == y[sa[i - ]] && sa[i] + k <= n && sa[i - ] + k <= n && y[sa[i] + k] == y[sa[i - ] + k] ? p : ++p;

        if(p == n) break;
        m = p;
    }
}
void build_height()
{
    int k = ;

    for(int i = ; i <= n; i++) rank[sa[i]] = i;
    for(int i = ; i <= n; i++)
    {
        if(k != ) k--;

        if(rank[i] == ) continue;

        int j = sa[rank[i] - ];
        while(s[j + k] == s[i + k]) k++;
        height[rank[i]] = k;
    }
}
void gather(int x,int y)
{
    x = find(x), y = find(y);

    if(x == y) return;

    if(x > y) std::swap(x, y);

    long long calc = std::max(max[x] * max[y], min[x] * min[y]);

    if(!cnt || calc > ans) ans = calc;

    cnt += (long long)size[x] * size[y];

    fa[y] = x, size[x] += size[y];
    max[x] = std::max(max[y], max[x]);
    min[x] = std::min(min[y], min[x]);
}
void prework()
{
    build_sa(), build_height();

    for(int i = ; i <= n; i++)
        newedge(height[i], i);

    for(int i = ; i <= n; i++)
    {
        fa[i] = i, size[i] = ;
        min[i] = max[i] = a[sa[i]];
    }
}
void solve()
{
    for(int i = n - ; i >= ; i--)
    {
        for(int j = head[i]; j ; j = edge[j].next)
            gather(edge[j].v, edge[j].v - );

        outc[i] = cnt, outa[i] = ans;
    }
    for(int i = ; i < n; i++)
    {
        write(outc[i]);
        putchar(' ');
        write(outa[i]), puts("");
    }
}
void init()
{
    read(n);

    scanf("%s", s + );
    for(int i = ; i <= n; i++) read(a[i]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("savour.in","r",stdin);
    freopen("savour.out","w",stdout);
#endif

    init();

    prework();

    solve();

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return ;
}