题面[NOI2015]品酒大会题目描述一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。在大会的晚餐上，调酒师Rainbow调制了\(n\)杯鸡尾酒。这\(n\)杯鸡尾酒排成一

题意简述定义后缀\(p,q\)是\(r\)相似的当且仅当\(\forall1\lei\ler,s_{p+i-1}=s_{q+i-1}\)。对于每一个\(0\ler<n\)，求出：有多少对\(r\)相似的后缀。每个后缀有权值\(a_i\)，求在所有\(r\)相似的后缀对\((p,q)\)中\(a_p\cdota_q\)的最大值。若不存在则答案为

P2178[NOI2015]品酒大会题解纪念一下第一道完全自己想出来的紫NOI题。思路由于r相似有单调性的性质，题目中也提示了这一点，考虑按\(height_i\)从大到小把所有相邻的\(sa\)数组内两个后缀合并，用并查集维护，发现第一问的答案就是\[\sum_{i是并查集的根}\binom{size_i}{2}