题解 P2178 【[NOI2015]品酒大会】
y2823774827y
2019-03-12 10:53:11
###
**$\Longrightarrow\Longrightarrow\Longrightarrow$[更好的阅读体验](https://www.cnblogs.com/y2823774827y/p/10515232.html)**
后缀数组一眼题系列
$r$相似用$height$数组处理，每次按$height$分裂区间，显然是有单调性的
所求的$r_0^{n-1}$，$O(n^2)$是过不了的
利用单调性，上烂大街的离线并查集
并查集要维护：大小,最大值,次大值,最小值,次小值(由于这里$a_i$为整数，所以答案可能由最小值与次小值贡献)
细节还是挺多的
```cpp
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long LL;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){ if(c=='-') f=-1; c=getchar(); }
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
return x*f;
}
const LL maxn=1e6+9,inf=(1e18+1);
LL n,ans,sum,va,m;
LL c[maxn],x[maxn],sa[maxn],y[maxn],size[maxn],fa[maxn],rk[maxn],hei[maxn],w[maxn],tmp[maxn][2];
LL mx[maxn],cx[maxn],mi[maxn],ci[maxn];
bool visit[maxn],vx[maxn],vi[maxn];
char s[maxn];
inline void Get_sa(){
for(LL i=1;i<=n;++i) ++c[x[i]=(LL)(s[i]-'a'+1)];
for(LL i=2;i<=m;++i) c[i]+=c[i-1];
for(LL i=n;i>=1;--i) sa[c[x[i]]--]=i;
for(LL len=1;len<=n;len<<=1){
LL num(0);
for(LL i=n-len+1;i<=n;++i) y[++num]=i;
for(LL i=1;i<=n;++i) if(sa[i]>len) y[++num]=sa[i]-len;
for(LL i=1;i<=m;++i) c[i]=0;
for(LL i=1;i<=n;++i) ++c[x[i]];
for(LL i=2;i<=m;++i) c[i]+=c[i-1];
for(LL i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
memcpy(y,x,sizeof(x));
x[sa[1]]=num=1;
for(LL i=2;i<=n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+len]==y[sa[i-1]+len])?num:++num;
if(num==n) break;
m=num;
}
for(LL i=1;i<=n;++i) rk[sa[i]]=i;
LL ret(0);
for(LL i=1;i<=n;++i){
if(ret) --ret;
LL j(sa[rk[i]-1]);
while(s[j+ret]==s[i+ret]) ++ret;
hei[rk[i]]=ret;
}
}
LL Get_f(LL x){ return fa[x]==x?x:fa[x]=Get_f(fa[x]); }
inline void Del(LL x){
sum-=((size[x]-1)*size[x])/2;
}
inline void Merge(LL x,LL y){
fa[x]=y;
if(mx[x]>mx[y]){
cx[y]=mx[y];
mx[y]=mx[x];
if(vx[x] && cx[x]>cx[y])
cx[y]=cx[x];
}else
cx[y]=(vx[y]?max(cx[y],mx[x]):mx[x]);
if(mi[x]<mi[y]){
ci[y]=mi[y];
mi[y]=mi[x];
if(vi[x] && ci[x]<ci[y])
ci[y]=ci[x];
}else
ci[y]=(vi[y]?min(ci[y],mi[x]):mi[x]);
vx[y]=vi[y]=true;
size[y]+=size[x];
sum+=((size[y]-1)*size[y]>>1);
ans=max(ans,max(mx[y]*cx[y],mi[y]*ci[y]));
}
vector<LL>mark[maxn];
int main(){
n=Read();
scanf(" %s",s+1);
for(LL i=1;i<=n;++i) w[i]=Read();
m=26; Get_sa();
for(LL i=1;i<=n;++i) mark[hei[i]].push_back(i);
for(LL i=1;i<=n;++i) fa[i]=i;
for(LL i=1;i<=n;++i){
mx[i]=mi[i]=w[i];
vx[i]=vi[i]=false;
}
ans=-inf;
for(LL i=1;i<=n;++i) size[i]=1;
for(LL i=n-1;i>=0;--i){
for(LL j=0;j<mark[i].size();++j){
LL x(sa[mark[i][j]]);
visit[x]=true;
LL sax(rk[x]), nxt(sa[sax+1]),pre(sa[sax-1]);
LL fy(Get_f(pre));
Del(x); Del(fy);
Merge(x,fy);
}
tmp[i][0]=sum; tmp[i][1]=(ans<=-inf?0:ans);
}
for(LL i=0;i<n;++i) printf("%lld %lld\n",tmp[i][0],tmp[i][1]);
return 0;
}
```