题目大意

给定一个长度为N字符串,Q个询问。每个询问包含个位置,表示以开头的的后缀,问这些后缀两两之间的LCP长度之和。数据范围:,

题解

SVT似乎是Suffix Virtual Tree的意思啊,虽然,我一看到这个题目,就想到了后缀自动机反向建立后缀树然后在虚树上统计,太难写了GG。

所以还是用后缀数组,先求出Height数组和Rank数组。对于询问,先按照Rank排序,用一个RMQ来维护相邻的字符串之间的LCP长度,然后再按照相邻LCP长度从大到小用并查集来合并即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#define LL long long
using namespace std;

const int Maxn=510000;

void radix(int str[],int pos[],int sa[],int n,int m){
    static int count[Maxn+5];
    memset(count,0,sizeof(count));
    for (int i=0;i<n;i++) ++count[str[pos[i]]];
    for (int i=1;i<=m;i++) count[i]+=count[i-1];
    for (int i=n-1;i>=0;i--) sa[--count[str[pos[i]]]]=pos[i];
}

int sa[Maxn+5];
void SA(int str[],int sa[],int n,int m){
    static int rnk[Maxn+5],a[Maxn+5],b[Maxn+5];
    for (int i=0;i<n;i++) rnk[i]=i;
    radix(str,rnk,sa,n,m);
    rnk[sa[0]]=0;
    for (int i=1;i<n;i++)
        rnk[sa[i]]=rnk[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);

    for (int k=1;k<=n;k<<=1){
        for (int j=0;j<n;j++){
            a[j]=rnk[j]+1;
            b[j]=((j+k)>=n)?0:rnk[j+k]+1;
            sa[j]=j;
        }
        radix(b,sa,rnk,n,n);
        radix(a,rnk,sa,n,n);
        rnk[sa[0]]=0;
        for (int j=1;j<n;j++)
            rnk[sa[j]]=rnk[sa[j-1]]+(a[sa[j]]!=a[sa[j-1]] || b[sa[j]]!=b[sa[j-1]]);
    }
}

int height[Maxn+5],rnk[Maxn+5];
inline void getHeight(int str[],int sa[],int rnk[],int height[],int n){
    int k=0;
    height[0]=0;
    for (int i=0;i<n;i++) rnk[sa[i]]=i;
    for (int i=0;i<n;i++){
        k=(k==0)?k:k-1;
        if (rnk[i]!=0) while(str[i+k]==str[sa[rnk[i]-1]+k]) ++k;
        height[rnk[i]]=k;
    }
}

int n,Q;
char str[Maxn+5];
int istr[Maxn+5];

int lg2[Maxn+5];

int stMin[Maxn+5][20];
inline void preLg2(int n){
    lg2[0]=-1;
    for (int i=1;i<=n;i++){
        lg2[i]=lg2[i>>1]+1;
    }
}

inline void preST(int n){
    for (int i=1;i<=n;i++) stMin[i][0]=height[i];
    for (int j=1;(1<<j)<=n;j++){
        for (int i=1;i+(1<<j)-1<=n;i++){
            stMin[i][j]=min(stMin[i][j-1],stMin[i+(1<<(j-1))][j-1]);
        }
    }
}
inline int queryMin(int left,int right){
    int len=right-left+1;
    int k=lg2[len];
    return min(stMin[left][k],stMin[right-(1<<k)+1][k]);
}

int idx[Maxn+5],val[Maxn+5];
LL ans=0;
int fa[Maxn+5],si[Maxn+5];
inline bool cmp(int a,int b){return val[a]>val[b];}
int getFather(int x){
    return fa[x]=(fa[x]==x?x:getFather(fa[x]));
}
void mergeFather(int x,int y,LL val){
    int fx=getFather(x),fy=getFather(y);
    if (fx==fy) return;
    ans+=(LL)val*(LL)si[fx]*si[fy];
    if (si[fx]>si[fy]){
        fa[fx]=fy;
        si[fy]+=si[fx];
    }else{
        fa[fy]=fx;
        si[fx]+=si[fy];
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&Q);
    preLg2(n);
    scanf("%s",str);

    for (int i=0;i<n;i++) istr[i]=str[i]-'a'+1;
    SA(istr,sa,n,26);
    getHeight(istr,sa,rnk,height,n);
    preST(n-1);

    for (int rt=1;rt<=Q;rt++){
        int siz; scanf("%d",&siz);
        for (int i=1;i<=siz;i++) scanf("%d",&idx[i]);
        for (int i=1;i<=siz;i++) idx[i]--;
        ans=0;
        for (int i=1;i<=siz;i++) idx[i]=rnk[idx[i]]+1;
        sort(idx+1,idx+siz+1);
        siz=unique(idx+1,idx+siz+1)-idx-1;

        for (int i=1;i<=siz;i++) fa[i]=i,si[i]=1;
        for (int i=1;i<siz;i++) val[i]=queryMin(idx[i],idx[i+1]-1);
        for (int i=1;i<siz;i++) idx[i]=i;
        sort(idx+1,idx+siz,cmp);
        for (int i=1;i<siz;i++) mergeFather(idx[i],idx[i]+1,val[idx[i]]);
        printf("%lld\n",ans);
    }
    return 0;
}

莫名地就跑了26S,还是SVT的方法会快一点吧,耸肩。

发表评论

电子邮件地址不会被公开。 必填项已用*标注