傳送門

傳送門

題意：給一個長度為$N$的字符串和一個長度為$N$的序列$A$，對于所有的$k\in [0,N?1]$，求選出兩個數$i,j$滿足$lcp(suffix(i),suffix(j))\ge k$的方案數和$A_i\times A_j$的最大值

數據范圍：暴力跑不過

終于有個后綴自動機做不了的了

看到后綴的前綴，顯然是后綴數組

顯然求出$height$數組，倒著排序

顯然這是單調的

讀到一個長度時，就把$i$和$i?1$合并并統計答案

顯然可以用并查集

對于方案數，維護一個$size$ ，合并的時候相乘再計入答案

對于$A_i\times A_j$的最大值，維護當前$A$的最大值和次大值

然而有負數。根據意識流，再維護個最小值和次小值

瞎維護一通，信仰$AC$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #define MAXN 300005 using namespace std; typedef long long ll; const ll INF=1e18; int sa[MAXN],rk[MAXN],tp[MAXN]; int c[MAXN],n,m='z'; int ht[MAXN]; char s[MAXN]; inline void Rsort() {for (int i=1;i<=m;i++) c[i]=0;for (int i=1;i<=n;i++) ++c[rk[i]];for (int i=1;i<=m;i++) c[i]+=c[i-1];for (int i=n;i>=1;i--) sa[c[rk[tp[i]]]--]=tp[i]; } void SA() {for (int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;Rsort();for (int w=1,p=0;p<n;m=p,w<<=1){p=0;for (int i=n-w+1;i<=n;i++) tp[++p]=i;for (int i=1;i<=n;i++) if (sa[i]>w) tp[++p]=sa[i]-w;Rsort();swap(rk,tp),rk[sa[1]]=p=1;for (int i=2;i<=n;i++)if (tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w]) rk[sa[i]]=p;else rk[sa[i]]=++p;}int p=0;for (int i=1;i<=n;i++){if (p) --p;int j=sa[rk[i]-1];while (s[i+p]==s[j+p]) ++p;ht[rk[i]]=p;} } int a[MAXN],p[MAXN]; int fa[MAXN]; int find(const int& x){return fa[x]==x? x:fa[x]=find(fa[x]);} ll mx[MAXN],sc[MAXN],mn[MAXN],cs[MAXN],siz[MAXN]; inline bool cmp(const int& a,const int& b){return ht[a]>ht[b];} ll ans[MAXN][2],tmp[2]; int main() {scanf("%d",&n);scanf("%s",s+1);SA();for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) siz[i]=1,fa[i]=p[i]=i,mx[i]=mn[i]=a[sa[i]],sc[i]=-INF,cs[i]=INF;sort(p+1,p+n+1,cmp);int cur=n-1;tmp[1]=-INF;for (int i=1;i<=n;i++){int x=find(p[i]),y=find(p[i]-1);tmp[0]+=siz[x]*siz[y];siz[x]+=siz[y];if (mx[y]>mx[x]) sc[x]=max(mx[x],sc[y]),mx[x]=mx[y];else if (mx[y]>sc[x]) sc[x]=mx[y];if (mn[y]<mn[x]) cs[x]=min(mn[x],cs[y]),mn[x]=mn[y];else if (mn[y]<cs[x]) cs[x]=mn[y];tmp[1]=max(tmp[1],max(mx[x]*sc[x],mn[x]*cs[x]));fa[y]=x;ans[ht[p[i]]][0]=tmp[0],ans[ht[p[i]]][1]=tmp[1];}for (int i=n-1;i>=0;i--) if (ans[i][0]==0&&ans[i][1]==-INF) ans[i][0]=ans[i+1][0],ans[i][1]=ans[i+1][1];for (int i=0;i<=n-1;i++) printf("%lld %lld\n",ans[i][0],ans[i][1]==-INF? 0:ans[i][1]);return 0; }

總結

以上是生活随笔為你收集整理的【NOI2015】品酒大会【后缀数组】【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。