【学术篇】NOI2015 品酒大会后缀数组+并查集

省选前大致是刷不了几道题了... 所以就找一些裸一点的题目练练板子算了= =

然而这题一点都不裸, 也并不怎么好写... 于是就浪费了将近一下午的时间... 然而还不是因为后缀数组板子不熟= =

首先这个"r相似"很显然就是lcp的值, 也就能想到后缀数组上的height... 不会后缀数组的先左转百度~

那么我们考虑如果有一个连续的区间, 它们的height值都是大于等于r的, 那么这段区间中的后缀两两"r相似".

而"r相似"的话, 也肯定有"r-1相似", "r-2相似", ... "0相似". 这样我们就会重复统计, 就会浪费时间. 所以我们不妨将这个连续的区间表示成一个点, 并查集!!

这样我们把id按照对应位置的height降序排序, 然后对于每个id, 我们把id-1这个点所在的区间和id所在的区间合并(根据height的含义, 就是表示sa[id]和sa[id-1]所对应的后缀的lcp长度..)

合并的同时维护信息即可. 说起来挺轻巧的, 其实不是很好懂.. (当然也可能是我太蒻了理解能力差)

最后不要忘了统计的时候做一个后缀和, 比r大的答案都要统计一下.

说的很不清楚(然而其实只是用来练板子谁曾想到这破题我写了一下午呢...)

有不懂的可以去看代码看了就更不懂了Emmmm

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=300050;

const long long INF=1ll<<62;

char s[N];

int fa[N],sz[N],mn[N],mx[N],w[N],id[N];

long long cnt[N],ans[N];

int x[N],y[N],sa[N],rnk[N],cc[N],height[N],len;

inline int gn(int a=0,char c=0,int f=1){

    for(;(c<'0'||c>'9')&&c!='-';c=getchar());

    if(c=='-') c=getchar(),f=-1;

    for(;c>47&&c<58;c=getchar()) a=a*10+c-48;

return a*f;}

bool hcmp(int x,int y){

    if(height[x]==height[y]) return x<y;

    return height[x]>height[y];

}

bool cmp(int *y,int a,int b,int k){

    int ra=a+k>=len?-1:y[a+k],rb=b+k>=len?-1:y[b+k];

    return y[a]==y[b]&&ra==rb;

}

void make_sa(){ int m=26;

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

    for(int i=0;i<len;++i) ++cc[x[i]=s[i]-'a'];

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

    for(int i=len-1;i>=0;--i) sa[--cc[x[i]]]=i;

    for(int k=1;k<=len;k<<=1){ int p=0;

        for(int i=len-k;i<len;++i) y[p++]=i;

        for(int i=0;i<len;++i) if(sa[i]>=k) y[p++]=sa[i]-k;

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

        for(int i=0;i<len;++i) ++cc[x[y[i]]];

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

        for(int i=len-1;i>=0;--i) sa[--cc[x[y[i]]]]=y[i];

        std::swap(x,y); m=1; x[sa[0]]=0;

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

            x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?m-1:m++;

        if(m>=len) break;

    }

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

}

void make_height(){ int k=0;

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

        if(!rnk[i]) continue;

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

        if(k) --k;

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

        height[rnk[i]]=k;

    }

}

int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x];}

void merge(int x,int y){

    sz[y]+=sz[x]; fa[x]=y;

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

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

}

int main(){

    len=gn();

    scanf("%s",s); len=strlen(s);

    make_sa(); make_height();

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

        w[i]=gn();

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

        fa[i]=i; id[i]=i;

        mx[i]=w[sa[i]]; mn[i]=w[sa[i]];

        sz[i]=1; ans[i]=-INF;

    } ::sort(id+1, id+len, hcmp);

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

        int x=find(id[i]-1),y=find(id[i]);

        cnt[height[id[i]]]+=1ll*sz[x]*sz[y];

        ans[height[id[i]]]=max(ans[height[id[i]]],1ll*mn[x]*mn[y]);

        ans[height[id[i]]]=max(ans[height[id[i]]],1ll*mn[x]*mx[y]);

        ans[height[id[i]]]=max(ans[height[id[i]]],1ll*mx[x]*mn[y]);

        ans[height[id[i]]]=max(ans[height[id[i]]],1ll*mx[x]*mx[y]);

        merge(x,y);

    }

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

        cnt[i]+=cnt[i+1],ans[i]=max(ans[i],ans[i+1]);

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

        printf("%lld %lld\n",cnt[i],cnt[i]?ans[i]:0);

}

巴特西

【学术篇】NOI2015 品酒大会后缀数组+并查集

最新文章

热门文章

巴特西

【学术篇】NOI2015 品酒大会 后缀数组+并查集

最新文章

热门文章

【学术篇】NOI2015 品酒大会后缀数组+并查集