[UOJ#131][BZOJ4199][NOI2015]品酒大会 后缀数组 + 并查集

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
    if(Head == tail) {
        int l = fread(buffer, 1, BufferSize, stdin);
        tail = (Head = buffer) + l;
    }
    return *Head++;
}
int read() {
    int x = 0, f = 1; char c = Getchar();
    while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
    while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
    return x * f;
}

#define maxn 300010
#define oo 1ll << 60
#define LL long long
int n, val[maxn];
char S[maxn];

int m, rank[maxn], height[maxn], Ws[maxn], sa[maxn];
bool cmp(int *a, int p1, int p2, int len) { return a[p1] == a[p2] && a[p1+len] == a[p2+len]; }
void ssort() {
	int *x = rank, *y = height;
	m = 0; for(int i = 1; i <= n; i++) Ws[i] = 0;
	for(int i = 1; i <= n; i++) Ws[x[i] = S[i]]++, m = max(m, (int)S[i]);
	for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
	for(int i = n; i; i--) sa[Ws[x[i]]--] = i;
	for(int pos = 0, j = 1; pos < n; j <<= 1, m = pos) {
		pos = 0;
		for(int i = n - j + 1; i <= n; i++) y[++pos] = i;
		for(int i = 1; i <= n; i++) if(sa[i] > j) y[++pos] = sa[i] - j;
		for(int i = 1; i <= m; i++) Ws[i] = 0;
		for(int i = 1; i <= n; i++) Ws[x[y[i]]]++;
		for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
		for(int i = n; i; i--) sa[Ws[x[y[i]]]--] = y[i];
		swap(x, y); pos = 1; x[sa[1]] = 1;
		for(int i = 2; i <= n; i++) x[sa[i]] = cmp(y, sa[i], sa[i-1], j) ? pos : ++pos;
	}
	return ;
}
void calch() {
	for(int i = 1; i <= n; i++) rank[sa[i]] = i;
	for(int i = 1, j, k = 0; i <= n; height[rank[i++]] = k)
		for(k ? k-- : 0, j = sa[rank[i]-1]; S[i+k] == S[j+k]; k++) ;
	return ;
}

int fa[maxn], siz[maxn], minv[maxn], maxv[maxn];
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }

int pos[maxn], cntv[maxn];
LL ansc[maxn], ansm[maxn];
LL max(LL a, LL b, LL c, LL x, LL y, LL z) {
	return max(max(max(a * b, b * c), a * c), max(max(x * y, y * z), x * z));
}
int main() {
	read(); n = 0;
	char tc = Getchar();
	while(!isalpha(tc)) tc = Getchar();
	while(isalpha(tc)) S[++n] = tc, tc = Getchar();
	for(int i = 1; i <= n; i++) val[i] = read();
	
	ssort();
	calch();
	for(int i = 2; i <= n; i++) cntv[height[i]]++, m = max(m, height[i]);
	for(int i = m; i >= 0; i--) cntv[i] += cntv[i+1];
	for(int i = n; i > 1; i--) pos[cntv[height[i]]--] = i;
	for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1, minv[i] = maxv[i] = val[sa[i]];
	for(int i = 0; i <= n; i++) ansm[i] = -oo;
//	for(int i = 1; i <= n; i++) printf("%d ", height[i]); putchar(‘\n‘);
	for(int i = 1; i <= n; i++) if(pos[i] > 1) {
//		printf("%d\n", pos[i]);
		int u = findset(pos[i]-1), v = findset(pos[i]);
		ansc[height[pos[i]]] += (LL)siz[u] * siz[v];
		ansm[height[pos[i]]] = max(ansm[height[pos[i]]], max((LL)minv[u] * minv[v], (LL)maxv[u] * maxv[v]));
		siz[u] += siz[v];
		minv[u] = min(minv[u], minv[v]); maxv[u] = max(maxv[u], maxv[v]);
		siz[v] = minv[v] = maxv[v] = 0;
		fa[v] = u;
	}
	
	for(int i = n - 1; i >= 0; i--) ansc[i] += ansc[i+1], ansm[i] = max(ansm[i], ansm[i+1]);
	for(int i = 0; i < n; i++) {
		if(!ansc[i]) ansm[i] = 0;
		printf("%lld %lld\n", ansc[i], ansm[i]);
	}
	
	return 0;
}