【NOI 2015】品酒大会

Problem

Description

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 \(n\) 杯鸡尾酒。这 \(n\) 杯鸡尾酒排成一行，其中第 \(i\) 杯酒 （\(1 \leq i \leq n\)） 被贴上了一个标签 \(s_i\)，每个标签都是 \(26\) 个小写英文字母之一。设 \(\mathrm{Str}(l, r)\) 表示第 \(l\) 杯酒到第 \(r\) 杯酒的 \(r − l + 1\) 个标签顺次连接构成的字符串。若 \(\mathrm{Str}(p, p_o) = \mathrm{Str}(q, q_o)\)，其中 \(1 \leq p \leq p_o \leq n\)，\(1 \leq q \leq q_o \leq n\)，\(p \neq q\)，\(p_o − p + 1 = q_o − q + 1 = r\)，则称第 \(p\) 杯酒与第 \(q\) 杯酒是“\(r\)相似” 的。当然两杯“\(r\)相似” （\(r > 1\)）的酒同时也是“\(1\) 相似”、“\(2\) 相似”、\(\dots\)、“\((r − 1)\) 相似”的。特别地，对于任意的 \(1 \leq p, q \leq n\)，\(p \neq q\)，第 \(p\) 杯酒和第 \(q\) 杯酒都是“\(0\)相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 \(i\) 杯酒 （\(1 \leq i \leq n\)） 的美味度为 \(a_i\)。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 \(p\) 杯酒与第 \(q\) 杯酒调兑在一起，将得到一杯美味度为 \(a_p a_q\) 的酒。现在请各位品酒师分别对于 \(r = 0,1,2, \dots, n − 1\)，统计出有多少种方法可以选出 \(2\) 杯“\(r\)相似”的酒,并回答选择 \(2\) 杯“\(r\)相似”的酒调兑可以得到的美味度的最大值。

Input Format

输入文件的第 \(1\) 行包含 \(1\) 个正整数 \(n\)，表示鸡尾酒的杯数。

第 \(2\) 行包含一个长度为 \(n\) 的字符串 \(S\)，其中第 \(i\) 个字符表示第 \(i\) 杯酒的标签。

第 \(3\) 行包含 \(n\) 个整数，相邻整数之间用单个空格隔开，其中第 \(i\) 个整数表示第 \(i\) 杯酒的美味度 \(a_i\)。

Output Format

输出文件包括 \(n\) 行。第 \(i\) 行输出 \(2\) 个整数，中间用单个空格隔开。第 \(1\) 个整数表示选出两杯“\((i − 1)\)相似”的酒的方案数，第 \(2\) 个整数表示选出两杯“\((i − 1)\)相似”的酒调兑可以得到的最大美味度。若不存在两杯“\((i − 1)\)相似”的酒，这两个数均为 \(0\)。

Sample

Input 1

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

Output 1

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0

Input 2

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

Output 2

66 120
34 120
15 55
12 40
9 27
7 16
5 7
3 -4
2 -4
1 -4
0 0
0 0

Explanation

Explanation for Input 1

用二元组 \((p, q)\) 表示第 \(p\) 杯酒与第 \(q\) 杯酒。

\(0\) 相似：所有 \(45\) 对二元组都是 \(0\) 相似的，美味度最大的是 \(8 \times 7 = 56\)。

\(1\) 相似：\((1,8)\) \((2,4)\) \((2,9)\) \((4,9)\) \((5,6)\) \((5,7)\) \((5,10)\) \((6,7)\) \((6,10)\) \((7,10)\)，最大的 \(8 \times 7 = 56\)。

\(2\) 相似：\((1,8)\) \((4,9)\) \((5,6)\)，最大的 \(4 \times 8 = 32\)。

没有 \(3,4,5, \dots,9\) 相似的两杯酒，故均输出 \(0\)。

Range

Case #	$n$ 的规模	$a_i$ 的规模	备注
1	$n = 100$	$\lvert a_i \rvert \leq 10000$	-
2	$n = 200$
3	$n = 500$
4	$n = 750$
5	$n = 1000$	$\lvert a_i \rvert \leq 1000000000$
6
7	$n = 2000$
8
9	$n = 99991$	$\lvert a_i \rvert \leq 1000000000$	不存在「$10$ 相似」的酒
10
11	$n = 100000$	$\lvert a_i \rvert \leq 1000000$	所有 $a_i$ 的值都相等
12	$n = 200000$
13	$n = 300000$
14
15	$n = 100000$	$\lvert a_i \rvert \leq 1000000000$	-
16
17	$n = 200000$
18
19	$n = 300000$
20

Algorithm

后缀数组，并查集

Mentality

首先看一下题目，后缀数组是真的挺显然的，而且范围也只会放 \(nlog\) 或是 \(nlog^2\) 的算法过而已。那么理理思绪，首先的话，题目里明里暗里都在说是按后缀的重合度来判断两杯酒的相似性，那么我们肯定先来一发后缀排序，使能重叠的后缀重叠数达到最高。

由于对于两杯酒，如果它们是 \(r\) 相似的，那么它们也必定是 \(k(k< r)\) 相似的，这题目里倒是告诉你了，虽然无比显然 \(......\)那么我们我们不难发现，如果我处理出了 \(r\) 相似的某个答案，那么它也就能够贡献到所有 \(k(k< r)\) 相似的答案里。

则我们处理的时候只需要按相邻后缀间的最大重合前缀处理答案就行，只需要注意对最后的答案记一遍后缀和即可(因为后面的所有答案都可以贡献到前面去)。

那么处理过程就变得单调了，我们考虑下一步怎么做。由于对于一对 \(len\) 相似的酒，它一定会在 \(1\) 至 \(len-1\) 相似的时候被枚举过，那么我们要考虑省去这个枚举 \(1\) 到 \(len-1\) 相似的答案的过程，否则复杂度还会是 \(n^2\) 的。

怎么做呢？首先可以发现，我们必须要由大到小来枚举 \(len\) ，否则无法省去，那我们不难想到，将后缀数组的 \(height\) 数组从大到小排序，然后从大到小处理。

这一步倒是简单，但是注意到，当我们处理到某个长度 \(height[i]=k(k< len)\) 的时候，如果后缀 \(i\) 与后缀 \(sa[rank[i]+1]\) 的重合长度恰好为 \(len>k\) 的时候，我们显然不能直接单纯地计算这个 \(height\) 数组相连的两个后缀，因为第 \(i\) 个后缀与第 \(sa[rank[i]+1]\) 个后缀它们也是可以对长度 \(k\) 的答案做出贡献的，而且这个贡献无关 \(len\) 的答案。

怎么办呢？于是我们发现，我们完全可以维护一个并查集，每次处理一个 \(height\) 数组就将它所代表的两个后缀放在一个并查集里，处理 \(height\) 数组的时候并不单纯处理两个后缀，而是处理两个后缀所在的并查集。

由于我们是按 \(height\) 数组从大到小处理的，所以对于我当前处理的一对重合度为 \(k\) 的后缀，它们所在的两个并查集内的后缀必定都是重合度大于等于 \(k\) 的，则也都可以计算贡献。

那么题目的解法就出来了：

• 后缀排序并处理出 \(height\) 数组。

• 按 \(height\) 从大到小的顺序来处理答案，每次将这两个后缀所在的并查集合并，并计算 \(height\) 相似的答案。

• 并查集维护 \(size\) ，最大值和最小值，之所以要维护最小值，就是因为题目内的权值可以为负数，两个很小的负数乘起来倒还是一个坑点。

• 对于答案的计算，则是每次合并两个并查集的时候，\(height\) 相似的数量类答案增加两个 \(size\) 的乘积，最大值答案在两个并查集的 \(max\) 乘积与 \(min\) 乘积中取最大值。

• 统计答案的后缀和与后缀最大值

Code

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int n, cnt, M = 27, a[300001], sa[300001], rk[300001], height[300001],
            tp[300001], tag[300001], fa[300001], size[300001], Max[300001],
            Min[300001], w[300001], id[300001];
char s[300002];
long long Ans[300002], amax[300001], sum[300002];
void Sort() {
  for (int i = 1; i <= M; i++) tag[i] = 0;
  for (int i = 1; i <= n; i++) tag[rk[i]]++;
  for (int i = 1; i <= M; i++) tag[i] += tag[i - 1];
  for (int i = n; i >= 1; i--) sa[tag[rk[tp[i]]]--] = tp[i];
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(int a, int b) { return height[a] > height[b]; }
void Merge(int a, int b, int len) {
  a = find(a), b = find(b);
  fa[b] = a;
  sum[len] += 1ll * size[a] * size[b];
  size[a] += size[b];
  amax[a] = max(
      amax[a], max(amax[b], max(1ll * Max[a] * Max[b], 1ll * Min[a] * Min[b])));
  Max[a] = max(Max[a], Max[b]);
  Min[a] = min(Min[a], Min[b]);
  Ans[len] = max(Ans[len], amax[a]);
}
int main() {
  cin >> n;
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  for (int i = 1; i <= n; i++) rk[i] = s[i] - 'a' + 1, tp[i] = i;
  Sort();
  for (int len = 1; cnt < n; len <<= 1, M = cnt) {
    cnt = 0;
    for (int i = n - len + 1; i <= n; i++) tp[++cnt] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > len) tp[++cnt] = sa[i] - len;
    Sort();
    swap(tp, rk);
    rk[sa[1]] = cnt = 1;
    for (int i = 2; i <= n; i++)
      rk[sa[i]] =
          tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + len] == tp[sa[i] + len]
              ? cnt
              : ++cnt;
  }  //后缀排序
  for (int i = 1, len = 0; i <= n; i++) {
    if (len) len--;
    int x = sa[rk[i] - 1];
    while (s[x + len] == s[i + len]) len++;
    height[rk[i]] = len;
  }  //求 height 数组
  for (int i = 1; i <= n; i++)
    Max[i] = Min[i] = w[i], amax[i] = Ans[i] = -1e18, id[i] = fa[i] = i,
    size[i] = 1;  //并查集与答案数组初始化
  Ans[n + 1] = Ans[0] = -1e18;
  sort(id + 2, id + n + 1, cmp);  //按 height 从大到小排序
  for (int i = 2; i <= n; i++)
    Merge(sa[id[i]], sa[id[i] - 1], height[id[i]]);  //合并两个后缀所在的并查集
  for (int i = n; i >= 0; i--)
    sum[i] += sum[i + 1], Ans[i] = max(Ans[i], Ans[i + 1]);  //答案统计后缀和
  for (int i = 0; i < n; i++)
    printf("%lld %lld\n", sum[i], !sum[i] ? 0 : Ans[i]);  //输出答案
}