[BZOJ4199][Noi2015]品酒大會（后綴數(shù)組+并查集）

2019-11-08 19:29:36

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題目描述

傳送門

題解

別出心裁的一道sa，想了好久。。

40pts

O(n2) $O(n^2)$ 的做法應(yīng)該很好想吧 sa+st表就可以了qwq

100pts

首先求出height數(shù)組考慮如果只求一個r的話怎么做顯然可以將height數(shù)組分組，每個組里都是height>=r的，然后對于每一個組計數(shù)+取max 那么如果有多個r呢？

顯然r大的要比r小的分的組少一些換句話說就是如果已經(jīng)將r分組，再將r-1分組的時候，可以往上一次分的組里插進(jìn)去一些也就是說可以r可以在r+1的基礎(chǔ)上統(tǒng)計先將height排序，然后從大到小枚舉，每一次將相同的r全部加入進(jìn)去不同的組可以用并查集維護(hù)（size，最大次大，最小次小），合并的時候只需要分別減去合并之前的答案然后再加上合并之后的答案就行了，求最大值不用減只用取max

時間復(fù)雜度O(nlogn+nα(n)?一坨常數(shù)) $O(nlogn+n/alpha(n)*一坨常數(shù))$ 代碼寫得好丑啊。。常數(shù)巨大

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 300005int n,m,now,r,lastr;char s[N];LL a[N];int *x,*y,X[N],Y[N],c[N],sa[N],height[N],rank[N];struct data{int id,len;}suf[N];int f[N];LL size[N],val[N][5],sel[10],ans[2][N];void build_sa(){ m=200; x=X,y=Y; for (int i=0;i<m;++i) c[i]=0; for (int i=0;i<n;++i) ++c[x[i]=s[i]]; for (int i=1;i<m;++i) c[i]+=c[i-1]; for (int i=n-1;i>=0;--i) sa[--c[x[i]]]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (int i=n-k;i<n;++i) y[p++]=i; for (int i=0;i<n;++i) if (sa[i]>=k) y[p++]=sa[i]-k; for (int i=0;i<m;++i) c[i]=0; for (int i=0;i<n;++i) ++c[x[y[i]]]; for (int i=0;i<m;++i) c[i]+=c[i-1]; for (int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for (int i=1;i<n;++i) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&(sa[i-1]+k<n?y[sa[i-1]+k]:-1)==(sa[i]+k<n?y[sa[i]+k]:-1)?p-1:p++; if (p>n) break; m=p; }}void build_height(){ for (int i=0;i<n;++i) rank[sa[i]]=i; int k=0; for (int i=0;i<n;++i) { if (!rank[i]) continue; if (k) --k; int j=sa[rank[i]-1]; while (i+k<n&&j+k<n&&s[i+k]==s[j+k]) ++k; height[rank[i]]=k; }}int cmp(data a,data b){ return a.len>b.len;}int find(int x){ if (x==f[x]) return x; f[x]=find(f[x]); return f[x];}void merge(int x,int y,int id){ int f1=find(x),f2=find(y); if (f1!=f2) { ans[0][id]-=size[f1]*(size[f1]-1LL)/2LL; ans[0][id]-=size[f2]*(size[f2]-1LL)/2LL; int cnt=0; for (int i=0;i<min((int)size[f1],4);++i) sel[cnt++]=val[f1][i]; for (int i=0;i<min((int)size[f2],4);++i) sel[cnt++]=val[f2][i]; size[f2]+=size[f1]; size[f1]=0; ans[0][id]+=size[f2]*(size[f2]-1LL)/2LL; f[f1]=f2; sort(sel,sel+cnt); if (size[f2]==2LL) { val[f2][0]=sel[1],val[f2][1]=sel[0]; ans[1][id]=max(ans[1][id],val[f2][0]*val[f2][1]); } else if (size[f2]==3LL) { val[f2][0]=sel[2],val[f2][1]=sel[1],val[f2][2]=sel[0]; ans[1][id]=max(ans[1][id],max(val[f2][0]*val[f2][1],val[f2][1]*val[f2][2])); } else { val[f2][0]=sel[cnt-1],val[f2][1]=sel[cnt-2],val[f2][2]=sel[1],val[f2][3]=sel[0]; ans[1][id]=max(ans[1][id],max(val[f2][0]*val[f2][1],val[f2][2]*val[f2][3])); } }}void add(data x){ if (x.id) merge(x.id,x.id-1,x.len); if (x.id<n-1&&height[x.id+1]>=r) merge(x.id,x.id+1,x.len);}int main(){ scanf("%d",&n); scanf("%s",s); for (int i=0;i<n;++i) scanf("%lld",&a[i]); build_sa(); build_height(); for (int i=0;i<n;++i) suf[i].id=i,suf[i].len=height[i]; sort(suf,suf+n,cmp); for (int i=0;i<n;++i) { f[i]=i,size[i]=1LL; val[i][0]=a[sa[i]],val[i][1]=val[i][2]=val[i][3]=0; } memset(ans[1],128,sizeof(ans[1])); now=0; while (now<n) { r=suf[now].len; ans[0][r]=ans[0][lastr]; while (now<n&&suf[now].len==r) { add(suf[now]); ++now; } lastr=r; } for (int i=n-1;i>=0;--i) { ans[0][i]=max(ans[0][i],ans[0][i+1]); ans[1][i]=max(ans[1][i],ans[1][i+1]); } for (int i=0;i<n;++i) { if (!ans[0][i]) puts("0 0"); else