NOI 2015 品酒大会 (后缀数组+并查集)

时间：2024-11-28 14:07:44

题目大意：略

40分暴力还是很好写的，NOI 2015 品酒大会 (后缀数组+并查集)差分再跑个后缀和 和 后缀最大值就行了

一种正解是后缀数组+并查集

但据说还有后缀数组+单调栈的高端操作蒟蒻的我当然不会

后缀数组求出height，然后从大到小排个序，那么每次把最大height的两个后缀放到一个并查集里

这样，每次根据height合并两个并查集的时候，一个并查集任何一个后缀和另一个并查集任何一个后缀的LCP长度都是height[i]

并查集维护集合内a[i]最大值，最小值(负负得正)，然后每次合并都打差分，统计答案的时候跑一遍后缀和和后缀最大值即可

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define N 301000

 #define rint register int

 #define inf 1000000000000000001ll

 using namespace std;

 //re

 int len;

 char str[N];

 int tr[N],rk[N],hs[N],sa[N],fa[N];

 ll a[N],ma[N],mi[N],ans[N],sum[N],p[N],sz[N];

 struct Height{int id,w;}h[N];

 int cmp(Height s1,Height s2){return s1.w>s2.w;}

 bool check(int k,int x,int y){

     if(x+k>len||y+k>len) return ;

     else return (rk[x]==rk[y]&&rk[x+k]==rk[y+k])?:;

 }

 void get_sa()

 {

     int cnt=;rint i;

     for(i=;i<=len;++i) hs[str[i]]++;

     for(i=;i<=;++i) if(hs[i]) tr[i]=++cnt;

     for(i=;i<=;++i) hs[i]+=hs[i-];

     for(i=;i<=len;++i) rk[i]=tr[str[i]],sa[hs[str[i]]--]=i;

     for(int k=;cnt<len;k<<=)

     {

         for(i=;i<=cnt;++i) hs[i]=;

         for(i=;i<=len;++i) hs[rk[i]]++;

         for(i=;i<=cnt;++i) hs[i]+=hs[i-];

         for(i=len;i>=;i--) if(sa[i]>k) tr[sa[i]-k]=hs[rk[sa[i]-k]]--;

         for(i=;i<=k;++i) tr[len-i+]=hs[rk[len-i+]]--;

         for(i=;i<=len;++i) sa[tr[i]]=i;

         for(i=,cnt=;i<=len;++i) tr[sa[i]]=check(k,sa[i],sa[i-])?cnt:++cnt;

         for(i=;i<=len;++i) rk[i]=tr[i];

     }

     for(i=;i<=len;++i){

         h[i].id=i;

         if(rk[i]==) continue;

         for(int j=max(,h[rk[i-]].w-);;j++)

             if(str[i+j-]==str[sa[rk[i]-]+j-]) h[rk[i]].w=j;

             else break;

     }

 }

 int find_fa(int x){

     int y=x;

     while(y!=fa[y]) y=fa[y];

     while(fa[x]!=y){

         int pre=fa[x];

         fa[x]=y;

         x=pre;

     }return y;

 }

 void solve()

 {

     rint i;int x,y,fx,fy;

     for(i=;i<=len;++i) sz[i]=,fa[i]=i,mi[i]=ma[i]=a[sa[i]];

     for(i=;i<=len;)

     {

         int j=h[i].w;

         for(;h[i].w>=j&&i<=len;i++){

             x=h[i].id-;fx=find_fa(x);

             y=h[i].id;fy=find_fa(y);

             p[j]+=sz[fx]*sz[fy];

             ans[j]=max(ans[j],max(mi[fx]*mi[fy],ma[fx]*ma[fy]));

             fa[fy]=fx,sz[fx]+=sz[fy];

             ma[fx]=max(ma[fx],ma[fy]),mi[fx]=min(mi[fx],mi[fy]);

         }

     }

 }

 int main()

 {

     scanf("%d",&len);

     scanf("%s",str+);

     for(int i=;i<=len;++i)

         scanf("%lld",&a[i]);

     memset(ans,-0x3f,sizeof(ans));

     get_sa();

     sort(h+,h+len+,cmp);

     solve();

     for(int i=len;i>=;i--)

         sum[i]=sum[i+]+p[i],ans[i]=max(ans[i],ans[i+]);

     for(int i=;i<len;i++)

         printf("%lld %lld\n",sum[i],(ans[i]<=-inf)?:ans[i]);

     return ;

 }

相关文章