AC. 梦想

frank_c1

[NOI 2015] 品酒大会

发布于2016年05月12日 | 暂无评论 | 847阅读 | 单调栈,后缀数组

题目描述

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

在大会的晚餐上,调酒师 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)