[BZOJ4199][Noi2015]品酒大会（后缀数组+并查集）

2019-11-08 19:29:36

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

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

40pts

O(n2) $O(n^2)$ 的做法应该很好想吧 sa+st表就可以了qwq

100pts

首先求出height数组考虑如果只求一个r的话怎么做显然可以将height数组分组，每个组里都是height>=r的，然后对于每一个组计数+取max 那么如果有多个r呢？

显然r大的要比r小的分的组少一些换句话说就是如果已经将r分组，再将r-1分组的时候，可以往上一次分的组里插进去一些也就是说可以r可以在r+1的基础上统计先将height排序，然后从大到小枚举，每一次将相同的r全部加入进去不同的组可以用并查集维护（size，最大次大，最小次小），合并的时候只需要分别减去合并之前的答案然后再加上合并之后的答案就行了，求最大值不用减只用取max

时间复杂度O(nlogn+nα(n)∗一坨常数) $O(nlogn+n/alpha(n)*一坨常数)$ 代码写得好丑啊。。常数巨大

代码

#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 PRintf("%lld %lld/n",ans[0][i],ans[1][i]); }}

上一篇：4.1 结构类型——枚举

下一篇：RestFul WebService的创建和使用实例