题目

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品

酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。在大会的晚餐上，调酒师Rainbow调制了 n 杯鸡尾酒。

这 n 杯鸡尾酒排成一行，其中第 i 杯酒 (1≤i≤n) 被贴上了一个标签 s_i ，每个标签都是 26 个小写英文字母

之一。设 Str(l,r) 表示第 l 杯酒到第 r 杯酒的 r-l+1 个标签顺次连接构成的字符串。若 Str(p,po)=Str(q,qo

) ，其中 1≤p≤po≤n,1≤q≤qo≤n,p≠q,po-p+1=qo-q+1=r ，则称第 p 杯酒与第 q 杯酒是“ r 相似”的。当

然两杯“ r 相似”(r>1)的酒同时也是“ 1 相似”、“ 2 相似”、……、“ (r-1) 相似”的。在品尝环节上，

品酒师Freda轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中

第 i 杯酒 (1≤i≤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 。

n=300,000 |a_i |≤1,000,000,000

输出格式

输出文件包括 n 行。第 i 行输出 2 个整数，中间用单个空格隔开。

第 1 个整数表示选出两杯“ (i-1)" " 相似”的酒的方案数，

第 2 个整数表示选出两杯“ (i-1) 相似”的酒调兑可以得到的最大美味度。

若不存在两杯“ (i-1) 相似”的酒，这两个数均为 0 。

输入样例

10

ponoiiipoi

2 1 4 7 4 8 3 6 4 7

输出样例

45 56

10 56

3 32

0 0

0 0

0 0

0 0

0 0

0 0

0 0

【样例说明1】

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

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

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

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

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

题解

这是一个后缀数组的题解

首先我们有一个暴力做法：

就是要我们求所有后缀的LCP，然后对于区间[0，LCP]出现次数+1，并对于区间[0,LCP]更新最大相乘权值

如果上后缀数组 + 线段树直接搞，那是\(O(n^2)\)的

我们考虑利用后缀数组的height数组

熟知后缀数组套路的都知道height数组 + 单调栈的套路

首先，由于大的长度答案也可以是小的长度的答案，所以我们一开始只用更新每对后缀LCP长度的答案，输出答案时从后往前更新一遍就可以了

就比如长度为8的出现了10次，长度为7的出现了7次，输出答案时就把8的加到7的去，长度为7的实际出现了17次

对于出现次数

我们用单调栈扫一遍后缀数组，当然对于当前到达的每个位置都要和栈内的元素一起更新答案

为了加快速度，我们入栈时记录入栈时间，出栈时再更新

由于每一个元素都要与栈内的元素一起更新，所以出栈时与[入栈位置，出栈位置]之间的所有元素一起进行更新答案就可以了

对于最大美味度，可以想到，一定是由两个最大的数相乘或两个最小的数相乘得来的

所以我们在单调栈中记录每一块的最大最小值，出栈时用ST表\(O(1)\)求出[入栈位置，出栈位置]之间的最值进行更新

总的\(O(nlogn)\)

撒花~~

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 300005,maxm = 100005;const LL INF = 1000000000000000000ll;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}char s[maxn];int sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],bac[maxn],n,m;void getsa(){ int *x = t1,*y = t2; m = 256; for (int i = 0; i <= m; i++) bac[i] = 0; for (int i = 1; i <= n; i++) bac[x[i] = s[i]]++; for (int i = 1; i <= m; i++) bac[i] += bac[i - 1]; for (int i = n; i; i--) sa[bac[x[i]]--] = i; for (int k = 1; k <= n; k <<= 1){ int p = 0; for (int i = n - k + 1; i <= n; i++) y[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k; for (int i = 0; i <= m; i++) bac[i] = 0; for (int i = 1; i <= n; i++) bac[x[y[i]]]++; for (int i = 1; i <= m; i++) bac[i] += bac[i - 1]; for (int i = n; i; i--) sa[bac[x[y[i]]]--] = y[i]; swap(x,y); p = x[sa[1]] = 1; for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p); if (p >= n) break; m = p; } for (int i = 1; i <= n; i++) rank[sa[i]] = i; for (int i = 1,k = 0; i <= n; i++){ if (k) k--; int j = sa[rank[i] - 1]; while (s[i + k] == s[j + k]) k++; height[rank[i]] = k; }}LL lcp[maxn],cnt[maxn],last[maxn],tmx[maxn],tmn[maxn],top;LL mx[maxn],sum[maxn],val[maxn];LL rmx[maxn][20],rmn[maxn][20],Log[maxn];void init(){ Log[0] = -1; mx[0] = -INF; for (int i = 1; i <= n; i++){ Log[i] = Log[i >> 1] + 1; rmx[i][0] = rmn[i][0] = val[sa[i]]; mx[i] = -INF; } for (int j = 1; j <= 19; j++){ for (int i = 1; i + (1 << j) - 1 <= n; i++){ rmx[i][j] = max(rmx[i][j - 1],rmx[i + (1 << j - 1)][j - 1]); rmn[i][j] = min(rmn[i][j - 1],rmn[i + (1 << j - 1)][j - 1]); } }}LL getmx(int l,int r){ int t = Log[r - l + 1]; return max(rmx[l][t],rmx[r - (1 << t) + 1][t]);}LL getmn(int l,int r){ int t = Log[r - l + 1]; return min(rmn[l][t],rmn[r - (1 << t) + 1][t]);}void solve(){ for (int i = 2; i <= n; i++){ int tot = 1; LL gmax = val[sa[i - 1]],gmin = val[sa[i - 1]]; while (top && lcp[top] >= height[i]){ sum[lcp[top]] += (LL)cnt[top] * (i - last[top]); mx[lcp[top]] = max(mx[lcp[top]],max(getmx(last[top],i - 1) * tmx[top],getmn(last[top],i - 1) * tmn[top])); gmax = max(gmax,tmx[top]); gmin = min(gmin,tmn[top]); tot += cnt[top--]; } lcp[++top] = height[i]; cnt[top] = tot; last[top] = i; tmx[top] = gmax; tmn[top] = gmin; } while (top){ sum[lcp[top]] += (LL)cnt[top] * (n + 1 - last[top]); mx[lcp[top]] = max(mx[lcp[top]],max(getmx(last[top],n) * tmx[top],getmn(last[top],n) * tmn[top])); top--; }}void print(){ for (int i = n - 1; i >= 0; i--) sum[i] += sum[i + 1],mx[i] = max(mx[i],mx[i + 1]); for (int i = 0; i < n; i++) printf("%lld %lld\n",sum[i],mx[i] == -INF ? 0 :mx[i]);}int main(){ n = read(); scanf("%s",s + 1); for (int i = 1; i <= n; i++) val[i] = read(); getsa(); init(); solve(); print(); return 0;}