题意

题目链接

Sol

说一个后缀自动机+线段树的无脑做法

首先建出SAM，然后对parent树进行dp，维护最大次大值，最小次小值

显然一个串能更新答案的区间是\([len_{fa_{x}} + 1, len_x]\)，方案数就相当于是从\(siz_x\)里面选两个，也就是\(\frac{siz_x (siz_x - 1)}{2}\)

直接拿线段树维护一下，标记永久化一下炒鸡好写~

#include<bits/stdc++.h>

#define int long long

#define LL long long

using namespace std;

const int MAXN = 1e6 + 10;

const LL INF = 2e18 + 10;

template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}

template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, a[MAXN];

char s[MAXN];

int root = 1, tot = 1, las = 1, ch[MAXN][26], fa[MAXN], len[MAXN], rev[MAXN];

LL mx[MAXN], mx2[MAXN], ans[MAXN], ans1[MAXN], mn[MAXN], mn2[MAXN], tmp[MAXN], siz[MAXN];

vector<int> v[MAXN];

void insert(int x, int id) {

	int now = ++tot, pre = las; las = now; siz[now] = 1; len[now] = len[pre] + 1; mx[now] = a[id]; mx2[now] = -INF; mn[now] = a[id]; mn2[now] = INF; rev[id] = now;

	for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;

	if(!pre) {fa[now] = root; return ;}

	int q = ch[pre][x];

	if(len[pre] + 1 == len[q]) fa[now] = q;

	else {

		int nq = ++tot; fa[nq] = fa[q]; len[nq] = len[pre] + 1;

		memcpy(ch[nq], ch[q], sizeof(ch[q]));

		fa[now] = fa[q] = nq;

		for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;

	}

}

void BuildDAG() {

	for(int i = 1; i <= tot; i++) assert(fa[i] != i), v[fa[i]].push_back(i);

}

int rt, Node, ls[MAXN], rs[MAXN], ad[MAXN], si[MAXN];

LL sum[MAXN], tag[MAXN];

void Build(int &k, int l, int r) {

	if(!k) k = ++Node, tag[k] = -INF, si[k] = r - l + 1;

	if(l == r) return ;

	int mid = l + r >> 1;

	Build(ls[k], l, mid);

	Build(rs[k], mid + 1, r);

}

void IntMax(int k, int l, int r, int ql, int qr, LL v) {

	if(ql <= l && r <= qr) {chmax(tag[k], v); return ;	}

	int mid = l + r >> 1;

	if(ql <= mid) IntMax(ls[k], l, mid, ql, qr, v);

	if(qr  > mid) IntMax(rs[k], mid + 1, r, ql, qr, v);

}

void IntAdd(int k, int l, int r, int ql, int qr, LL v) {

	if(ql <= l && r <= qr) {sum[k] += v; return ;}

	int mid = l + r >> 1;

	if(ql <= mid) IntAdd(ls[k], l, mid, ql, qr, v);

	if(qr  > mid) IntAdd(rs[k], mid + 1, r, ql, qr, v);

}

LL QueryNum(int k, int l, int r, int pos) {

	if(!k) return 0;

	LL now = sum[k];

	if(l == r || !k) return now;

	int mid = l + r >> 1;

	if(pos <= mid) now += QueryNum(ls[k], l, mid, pos);

	else now += QueryNum(rs[k], mid + 1, r, pos);

	return now;

}

LL QueryMax(int k, int l, int r, int pos) {

	if(!k) return -INF;

	LL now = tag[k];

	if(l == r || !k) return now;

	int mid = l + r >> 1;

	if(pos <= mid) chmax(now, QueryMax(ls[k], l, mid, pos));

	else chmax(now, QueryMax(rs[k], mid + 1, r, pos));

	return now;

}

void dfs(int x) {

	for(auto &to : v[x]) {

		dfs(to);

		siz[x] += siz[to];

		if(mx2[to] > mx[x]) chmax(mx2[x], mx[x]), mx[x] = mx2[to];

		else chmax(mx2[x], mx2[to]);

		if(mx[to] > mx[x]) chmax(mx2[x], mx[x]), mx[x] = mx[to];

		else chmax(mx2[x], mx[to]);

		if(mn2[to] < mn[x]) chmin(mn2[x], mn[x]), mn[x] = mn2[to];

		else chmin(mn2[x], mn2[to]);

		if(mn[to] < mn[x]) chmin(mn2[x], mn[x]), mn[x] = mn[to];

		else chmin(mn2[x], mn[to]);

	}

	if(siz[x] > 1 && x != root) {

		IntMax(rt, 1, N, len[fa[x]] + 1, len[x], mx[x] * mx2[x]);

		IntMax(rt, 1, N, len[fa[x]] + 1, len[x], mn[x] * mn2[x]);

		IntAdd(rt, 1, N, len[fa[x]] + 1, len[x], 1ll * siz[x] * (siz[x] - 1) / 2);

	}

}

signed main() {

	N = read();

	Build(rt, 1, N);

	scanf("%s", s + 1);

	reverse(s + 1, s + N + 1);

	for(int i = 1; i <= N; i++) tmp[i] = a[i] = read(), assert(a[i] != 0);

	reverse(a + 1, a + N + 1);

	for(int i = 1; i <= N; i++) insert(s[i] - 'a', i);

	for(int i = 1; i <= tot; i++) {

		ans[i] = -INF;

 		if(!mx[i]) mx[i] = -INF;

		if(!mx2[i]) mx2[i] = -INF;

		if(!mn[i]) mn[i] = INF;

		if(!mn2[i]) mn2[i] = INF;

	}

	BuildDAG();

 	dfs(1);

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

		ans1[i] = QueryNum(root, 1, N, i);

		ans[i] = QueryMax(root, 1, N, i);

	}

	sort(tmp + 1, tmp + N + 1, greater<int>());

	cout << 1ll * N * (N - 1) / 2 << " " << max(tmp[1] * tmp[2], tmp[N] * tmp[N - 1]) << '\n';

 	for(int i = 1; i < N; i++) cout << ans1[i] <<  " " << (ans[i] <= -INF ? 0 : ans[i]) << '\n';

    return 0;

}

/*

2

aa

-100000000 100000000

12

abaabaabaaba

1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

*/