题目描述

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

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

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

输入格式

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

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

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

$1 \le n \le 300000,|a_i| \le 10 ^ 9$

输出格式

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

题目解析

NOI的难度真是越来越接近NOIP了。

先解决第一个子问题。题目要求对于每一个$k$，求出有多少对$(i,j)$，满足$LCP(i,j) \ge k$。只需要求出$LCP(i,j) = k$的答案，再求一下后缀和就好。我们先求出$S$的后缀数组和$height$数组，有$LCP(i,j) = \min_{k=rank_i} ^ {rank_j-1} {height_k}$。可以用单调栈处理一下$height_i$向左和向右的影响范围$L,R$，则其对答案的贡献为$(i - L + 1) \cdot (R - i)$。这一部分时间复杂度$O(n \log n)$。

考虑第二个子问题。设$height_i$的影响范围为左边$[L,i]$，右边$[i+1,R]$，则问题等价于在$[L,i]$和$[i+1,R]$中分别选择一个整数，使它们的乘积最大。因为有负数的存在，讨论的情况比较多：

1.若左区间和右区间均有正值，用左区间最大值和右区间的最大值乘积更新答案。

2.若左区间和右区间均有负值，用左区间最小值和右区间的最小值乘积更新答案。

3.若左区间和右区间一侧均为正值，一侧均为负值，用正值区间最小值和负值区间的最大值乘积更新答案。

4.若左区间和右区间有一侧存在零值，用0更新答案。

我们可以维护4棵线段树来实现上述操作。为减小常数，我是用zkw线段树实现的。这一部分时间复杂度$O(n \log n)$。

总时间复杂度$O(n \log n)$。