题解 P2178 【[NOI2015]品酒大会】
shadowice1984 · · 题解
后缀数组X后缀树
(后缀的表示，对于字符串S，数字i表示从i位置开始的后缀) 无论是后缀数组还是后缀自动机，都是名为"后缀树"的数据结构的一种压缩
什么是后缀树呢，我们把字符串S的每一个后缀插入到trie树里，那么后缀树的每一个节点对应着S的一个子串，后缀树的每一个叶子节点对应着原串的一个后缀，两个后缀的lcp长度就是两个后缀对应节点在后缀树上的lca深度。
但是我们发现尽管后缀可以方便的处理各个后缀间的关系，判子串找lcp什么的也非常好使，但是我们发现后缀树的节点个数是O(n^2)的，因此我们需要将后缀树进行"压缩"，后缀数组就是压缩技术中的一种
后缀数组原理
我们发现我们知道所有子串的信息有点贪了……大部分时候我们只需要将子串理解为某个后缀的前缀即可，因此非常有用的是关于后缀的信息，然后我们发现，后缀只有O(N)个，而且，后缀树有一个非常重要的性质，如果后缀a的字典序小于后缀b的字典序，那么a的后缀树上对应节点的dfs序也是小于b的dfs序的，因此，我们如果可以将后缀按字典序排序，就可以部分还原后缀树的信息，而有些时候这些信息就是我们需要的，其实有点像虚树，不建树却可以实施某些树上操作
那么开始讲如何将后缀排序吧，首先说明O(N)的DC3我是不会的，我只会O(NlogN)的倍增做法，这道题3*10^5的只能说是勉强卡过去，所以请在实现的时候注意常数~
基数排序X桶排序/计数排序
（如果你认真读过算导的排序算法部分，可以跳过这个部分，但是如果只是了解的话，还是来看看吧……）
倍增实现法要求一个复杂度为O(N)的稳定排序，那么什么sort之类的就不用想了……，可以做到这个只有基数排序和桶排序以及计数排序，而基数排序又需要一个复杂度为O(N)的稳定排序，那么就只剩下桶排和计排了，事实上，用哪种都可以……，但是推荐使用计排，因为桶排常数大……，这道题你卡不过去30w的点的
先介绍啥叫计数排序，计数排序基于这一点，要排的数，值域不会太大，所以，我们可以枚举元素的值，计算每个值的排名,然后我们的思路是对于每个值，先计算一波有多少个元素就是这个值，记sum[i]表示值为i的元素个数。
之后，我们对sum[]做一个前缀和，这样的话，实际上是计算出来每个值的最后一个元素在排序后数组里的下标(注意一件事，当我们说排名，意味着相同值的元素排名相同，但是我们说数组下标的时候，这意味每一个元素的下标都是不同的)
为了起到稳定的效果，我们从后往前扫一遍待排序数组，将其放在它的值对应的下标上，为此我们需要复制下原数组，以免洗掉不该洗的东西，在此期间，sum[i]始终表示值为i的元素在排好序后数组的下标，当我们碰到了第一个值为i的元素时，我们会发现，因为倒着扫的缘故，它其实是原数组中最靠后的元素，它就应该待在sum[i]上，但是倒数第二个值为i的元素就不能待在sum[i]上了 为此我们让sum[i]--就可以了，就是把下一个元素放在这个元素左边的位置上。 这样我们就可以实现O(N+K)(K为值域)的排序了
另一种方式是桶排序，按理来讲应该是除法散列的……但是我们这里假设值域不是很大，因此我们可以选择散列函数H(x)=x,(看！绝对没冲突的hash！)
具体思路如下，正向扫一遍，我们开上K个队列(K为值域),然后我们把每个值为i的元素push进第i个队列里，最后从大到小的扫一遍队列数组，每次碰到一个队列，把它pop空，倒进待排序数组中，由于队列先进先出，相当于隐性的第二关键字为位置，也就起到了稳定的目的
下面是基数排序，我们知道，对于一些D位数，相当于最高位第一关键字，次高位第二关键字，一直到第D关键字，于是我们从低位到高位，每次以当前位为关键字进行稳定排序由于是稳定排序，因此第K轮其实是以第K位为第一关键字，K-1位为第二关键字，这样迭代起来，就是位数越高，优先级越大，就实现了排好这些N位数的目的。如果我们选择一个复杂度为O(N)的稳定排序(计排/桶排)作为基排的底层排序，就能做到O(D*N)的复杂度，并且，还是稳定的，因为第一位排序以第一位为第一关键字，位置为第二关键字。
倍增法
倍增法的思路，既然要排后缀，我们观察后缀的比较规则，从前向后比，那么我们可以先比第1位，再比第2位……且慢，难道我们真的要比N次？我们发现比完第2为之后，我们是可以知道每个长度为2的子串的排名的，因此，我们可以将两个子串拼接起来，先比前一半再比后一半，从而得出长度为4的子串的排名，得出长度为4的排名之后，再去排长度为8的，如此，直到长度超过N子串就成了后缀
那么每次，我们可以将子串的前一半排名变成第一关键字，后一半排名作为第二关键字，丢进去做基数排序，处理出排名，继续迭代，这就是倍增法了。
如何计算lcp
我们啊，会发现一个非常有趣的性质，设排好序之后的后缀构成的数组为sa[] 如果我们令ht[i]=lcp(sa[i],sa[i-1]);令rk[sa[i]]=i 那么有ht[rk[i]]>=ht[rk[i-1]]-1，之后我们就可以愉快的暴力求ht了 可以认为是求出后缀树上dfs序相邻两个节点lca深度
到目前为止，和虚树干的事没差别，求dfs序，相邻dfs序搞lca 对于两个后缀p,q,lcp(p,q)=rmq(sa[p],sa[q])(区间min)，所以要求任意的话st表预处理就行，查询O(1)
本题解法
对这个字符串求一发后缀数组，(底层排序用计排！！！桶排常数大会T飞)
那么我们发现如果我们可以维护一个集合，其中的后缀两两R相似该多好，答案瞬间出来了，C(siz,2)，以及max(最大*次大，最小*次小) 而且我们还发现一个美妙的性质，如果有一个后缀，和其中的某个元素r相似，那么和集合中的所有元素r相似，等等，这个性质好像可以用并查集维护~
那么求出来的后缀数组告诉我们一些串的最大相似程度，(lcp(sa[i],sa[i-1])=ht[i])那么我们就可以用并查集去维护r相似信息，具体来讲，把h大到小排序，每次并查集并起来r相似的两个串，在切换r的时候，更新一发答案即可。
记得开 long long
上代码~
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
char mde[300010];long long val[300010];
int sa[300010];int ra[600010];
int x[300010];int y[300010];int ht[300010];
int n;long long up;
int sum[300010];int tr[300010];
inline void rixs()//基排~,这里认为是两位数,每一位取值范围0-n
{
for(int i=1;i<=n;i++){sum[i]=0;}//清空sum
for(int i=1;i<=n;i++){sum[y[i]]++;}
for(int i=1;i<=n;i++){sum[i]+=sum[i-1];}//计排第一位
for(int i=n;i>=1;i--){sa[sum[y[i]]--]=i;}//计排放下去
for(int i=1;i<=n;i++){sum[i]=0;}//清sum
for(int i=1;i<=n;i++){sum[x[sa[i]]]++;}//计排第二位
for(int i=1;i<=n;i++){sum[i]+=sum[i-1];}
for(int i=1;i<=n;i++){tr[i]=sa[i];}//这里要复制存在sa里的位置信息
for(int i=n;i>=1;i--){sa[sum[x[tr[i]]]--]=tr[i];}//计排第二位放下去
ra[sa[1]]=1;for(int i=2;i<=n;i++)//计算rk,这里可以写个cmp再用条件表达式,我懒得写了
{if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]])ra[sa[i]]=ra[sa[i-1]];else ra[sa[i]]=i;}
}
inline void create_sa()
{
for(int i=1;i<=n;i++){sum[mde[i]-'a'+1]++;}//首先先强制转数字
for(int i=1;i<=26;i++){sum[i]+=sum[i-1];}//还是计排
for(int i=n;i>=1;i--){sa[sum[mde[i]-'a'+1]--]=i;}
ra[sa[1]]=1;for(int i=1;i<=n;i++)//一样的算排名
{if(mde[sa[i]]==mde[sa[i-1]])ra[sa[i]]=ra[sa[i-1]];else ra[sa[i]]=i;}
for(int k=1;k<=n;k<<=1)//倍增现在要排的子串长度
{
for(int i=1;i<=n;i++)x[i]=ra[i];//前一半第一关键字
for(int i=1;i<=n;i++)y[i]=ra[i+k];//后一半第二关键字
rixs();//基排
}return;
}
inline void calch()
{
int j=0;int k=0;
for(int i=1;i<=n;ht[ra[i++]]=k)//维护开始匹配的位置,暴力匹配即可
for(k=k?k-1:k,j=sa[ra[i]-1];mde[i+k]==mde[j+k];k++);
}
struct bcj//要开longlong,按址合并路径压缩还是都用上吧,毕竟单用都是log的
{
int fa[300010];int size[300010];
long long ma[300010];long long nxtma[300010];
long long mi[300010];long long nxtmi[300010];
inline void ih()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;size[i]=1;
ma[i]=val[sa[i]];nxtma[sa[i]]=-up;
mi[i]=val[sa[i]];nxtmi[sa[i]]=up;
}
}
inline void rfrma(long long x,int p)//刷新最大,次大值
{if(x>=ma[p]){nxtma[p]=ma[p];ma[p]=x;}else if(x>nxtma[p]){nxtma[p]=x;}}
inline void rfrmi(long long x,int p)//刷新最小,次小值
{if(x<=mi[p]){nxtmi[p]=mi[p];mi[p]=x;}else if(x<nxtmi[p]){nxtmi[p]=x;}}
inline int f(int x)
{return fa[x]=(fa[x]==x)?x:f(fa[x]);}
inline void u(int x,int y)
{
int u=f(x);int v=f(y);if(size[u]<size[v])swap(u,v);
size[u]+=size[v];fa[v]=u;
rfrma(ma[v],u);rfrma(nxtma[v],u);
rfrmi(mi[v],u);rfrmi(nxtmi[v],u);
}
inline long long get_size(int x){return size[f(x)];}
inline long long get_ma(int x)
{int u=f(x);return max(ma[u]*nxtma[u],mi[u]*nxtmi[u]);}
}s;
struct data//这里用来排序h的结构体
{
int n;int t;
friend bool operator <(data a,data b){return a.t>b.t;}
}d[300010];long long ans1[300010];long long ans2[300010];
int main()
{
up=pow(2LL,62);
scanf("%d",&n);scanf("%s",mde+1);
for(int i=1;i<=n;i++)scanf("%lld",&val[i]);
create_sa();calch();s.ih();
for(int i=1;i<=n;i++)d[i].n=i,d[i].t=ht[i];//排序h的时候保留一个索引
for(int i=1;i<=n;i++)ans2[i]=-up;
sort(d+1,d+n+1);int num=d[1].t;//维护当前更新什么答案
for(int i=1;i<=n;i++)
{
if(num!=d[i].t)//可能出现根本没有这个r的情况,此时答案同上
{for(int j=d[i].t;j<num;j++)ans1[j]=ans1[num],ans2[j]=ans2[num];num=d[i].t;}
if(s.f(d[i].n)!=s.f(d[i].n-1))//并的时候更新答案,省的统计啥时候切ht
{
ans1[num]+=s.get_size(d[i].n)*s.get_size(d[i].n-1);//这里换了个写法统计点对
s.u(d[i].n,d[i].n-1);ans2[num]=max(ans2[num],s.get_ma(d[i].n));//同时更新答案
}
}
for(int i=0;i<=n-1;i++)//倒着输出答案
{
if(ans1[i]==0){printf("0 0\n");continue;}
printf("%lld %lld\n",ans1[i],ans2[i]);
}
return 0;//拜拜程序~
}