BZOJ 4199: [Noi2015]品酒大会 [后缀数组 带权并查集]

时间：2023-03-08 19:22:01
BZOJ 4199: [Noi2015]品酒大会 [后缀数组 带权并查集]

4199: [Noi2015]品酒大会

UOJ：http://uoj.ac/problem/131

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 n 杯鸡尾酒。这 n 杯鸡尾酒排成一行，其中第 i 杯酒 （1≤i≤n） 被贴上了一个标签 si，每个标签都是 26 个小写英文字母之一。设 Str(l,r) 表示第 l 杯酒到第 r 杯酒的 r−l+1 个标签顺次连接构成的字符串。若 Str(p,po)=Str(q,qo)，其中 1≤p≤po≤n，1≤q≤qo≤n，p≠q，po−p+1=qo−q+1=r，则称第 p 杯酒与第 q 杯酒是“r相似” 的。当然两杯“r相似” （r>1）的酒同时也是“1 相似”、“2 相似”、…、“(r−1) 相似”的。特别地，对于任意的 1≤p,q≤n，p≠q，第 p 杯酒和第 q 杯酒都是“0相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 i 杯酒 （1≤i≤n） 的美味度为 ai。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 p 杯酒与第 q 杯酒调兑在一起，将得到一杯美味度为 apaq 的酒。现在请各位品酒师分别对于 r=0,1,2,…,n−1，统计出有多少种方法可以选出 2 杯“r相似”的酒,并回答选择 2 杯“r相似”的酒调兑可以得到的美味度的最大值。

输入格式

输入文件的第 1 行包含 1 个正整数 n，表示鸡尾酒的杯数。

第 2 行包含一个长度为 n 的字符串 S，其中第 i 个字符表示第 i 杯酒的标签。

第 3 行包含 n 个整数，相邻整数之间用单个空格隔开，其中第 i 个整数表示第 i 杯酒的美味度 ai。

输出格式

输出文件包括 n 行。第 i 行输出 2 个整数，中间用单个空格隔开。第 1 个整数表示选出两杯“(i−1)相似”的酒的方案数，第 2 个整数表示选出两杯“(i−1)相似”的酒调兑可以得到的最大美味度。若不存在两杯“(i−1)相似”的酒，这两个数均为 0。

linkct讲课时说了一种他考场上写的单调栈做法，忘了.....

比较经典的用并查集配合后缀数组吧

从大到小枚举LCP的长度L，把所有当前LCP长度的元素所在集合合并成一个集合

这时候每个集合里元素的LCP都是>=L,也就是都是L相似

合并的时候维护mx[i],mn[i],size[i]就好了

ans1[L]+=size[x]*size[y];
ans2[L]=max(ans2[L],max(mn[x]*mn[y],mx[x]*mx[y]));

注意i+1相似也是i相似，所以ans要处理后缀和

一点经验：

并查集直接用的是排序后编号

把相同LCP的放在一起可以用邻接链表

注意：

预处理时mx[i]=mn[i]=a[sa[i]]！！！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=3e5+;

typedef long long ll;

const ll INF=1e18+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,a[N];

char s[N];

struct edge{

    int v,ne;

}e[N];

int cnt,h[N];

inline void ins(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

}

int sa[N],rnk[N],t1[N],t2[N],height[N],c[N];

bool cmp(int *r,int a,int b,int j){

    return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];

}

void getSA(int m){

    int *r=t1,*k=t2;

    for(int i=;i<=n;i++) c[r[i]=s[i]]++;

    for(int i=;i<=m;i++) c[i]+=c[i-];

    for(int i=n;i>=;i--) sa[c[r[i]]--]=i;

    for(int j=;j<=n;j<<=){

        int p=;

        for(int i=n-j+;i<=n;i++) k[++p]=i;

        for(int i=;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;

        for(int i=;i<=m;i++) c[i]=;

        for(int i=;i<=n;i++) c[r[k[i]]]++;

        for(int i=;i<=m;i++) c[i]+=c[i-];

        for(int i=n;i>=;i--) sa[c[r[k[i]]]--]=k[i];

        swap(r,k);p=;r[sa[]]=++p;

        for(int i=;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-],j)?p:++p;

        if(p>=n) break;m=p;

    }

}

void getHeight(){

    for(int i=;i<=n;i++) rnk[sa[i]]=i;

    int k=;

    for(int i=;i<=n;i++){

        if(k) k--;

        if(rnk[i]==) continue;

        int j=sa[rnk[i]-];

        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;

        height[rnk[i]]=k;

    }

}

int fa[N],size[N];

ll ans1[N],ans2[N],mn[N],mx[N];

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void unn(int x,int y,int L){//printf("unn %d %d %d\n",x,y,L);

    x=find(x);y=find(y);

    if(x==y) return;

    //if(x<y) swap(x,y);

    ans1[L]+=(ll)size[x]*size[y];

    ans2[L]=max(ans2[L],max(mn[x]*mn[y],mx[x]*mx[y]));

    fa[x]=y;

    mx[y]=max(mx[y],mx[x]);

    mn[y]=min(mn[y],mn[x]);

    size[y]+=size[x];

}

void solve(){

    for(int i=;i<=n;i++){

        fa[i]=i,size[i]=,mx[i]=mn[i]=a[sa[i]],ans2[i]=-INF;

        if(i!=) ins(height[i],i);

    }

    for(int l=n-;l>=;l--){

        for(int i=h[l];i;i=e[i].ne) unn(e[i].v-,e[i].v,l);

        if(l!=n-){

            ans1[l]+=ans1[l+];

            ans2[l]=max(ans2[l],ans2[l+]);

        }

    }

    for(int i=;i<=n-;i++) printf("%lld %lld\n",ans1[i],ans2[i]==-INF?:ans2[i]);

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();

    scanf("%s",s+);

    for(int i=;i<=n;i++) a[i]=read();

    getSA();

    getHeight();

    solve();

}

相关文章