BZOJ-3879: SvT

Description

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].
现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.,且.

后缀数组求height数组，求所给串相邻两项的LCP，问题转化为一个序列的所有子区间的最小值之和。单调栈处理一下每个位置作为最小值所对应的子区间个数即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000 
typedef long long ll;
const ll mod=23333333333333333ll;
int n,m,t,a[3001000],Log[N],rm[N][22],z[N],L[N],R[N],b[N],top;
char s[N];
int r[N],sa[N],ran[N],hei[N];
void suffix_array(int len,int lp)
{
    int i,j,k;
    static int x[N<<1],y[N<<1],ws[N];
    memset(ws,0,sizeof(int)*lp);
    for(i=0;i<len;++i) ws[x[i]=r[i]]++;
    for(i=1;i<lp;++i) ws[i]+=ws[i-1];
    for(i=len-1;i>=0;--i) sa[--ws[x[i]]]=i;
    for(j=k=1;k<len;j<<=1,lp=k)
    {
        for(k=0,i=len-j;i<len;++i) y[k++]=i;
        for(i=0;i<len;++i) if(sa[i]>=j) y[k++]=sa[i]-j;
        memset(ws,0,sizeof(int)*lp);
        for(i=0;i<len;++i) ws[x[i]]++;
        for(i=1;i<lp;++i) ws[i]+=ws[i-1];
        for(i=len-1;i>=0;--i) sa[--ws[x[y[i]]]]=y[i];
        for(swap(x,y),i=k=1,x[sa[0]]=0;i<len;++i)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?k-1:k++;
    }
    for(i=1;i<len;++i) ran[sa[i]]=i;
    for(i=k=0;i<len-1;hei[ran[i++]]=k)
        for((k?--k:0),j=sa[ran[i]-1];r[i+k]==r[j+k];++k);
}

int lcp(int x,int y)
{
    x=ran[x]; y=ran[y];
    int lo=Log[y-x]; x++;
    return min(rm[x][lo],rm[y-(1<<lo)+1][lo]);
}

bool cmp(int x,int y){return ran[x]<ran[y];}
int main()
{
    scanf("%d%d%s",&n,&m,s);
    int i,j;
    for(i=0;i<n;++i) r[i]=s[i]-'a'+1;
    suffix_array(n+1,27);
    for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(i=1;i<=n;++i) rm[i][0]=hei[i];
    for(i=1;i<=Log[n];++i)
        for(j=1;j+(1<<i)-1<=n;++j)
            rm[j][i]=min(rm[j][i-1],rm[j+(1<<(i-1))][i-1]);
    while(m--)
    {
        scanf("%d",&t);
        for(i=1;i<=t;++i) scanf("%d",a+i),--a[i];
        sort(a+1,a+t+1,cmp);
        t=unique(a+1,a+t+1)-a-1;
        for(i=1;i<t;++i) b[i]=lcp(a[i],a[i+1]);
        --t;
        for(z[top=0]=0,i=1;i<=t;++i)
        {
            while(top&&b[i]<b[z[top]]) --top;
            L[i]=i-z[top]; z[++top]=i;
        }
        for(z[top=0]=t+1,i=t;i>0;--i)
        {
            while(top&&b[i]<=b[z[top]]) --top;
            R[i]=z[top]-i; z[++top]=i;
        }
        ll ans=0;
        for(i=1;i<=t;++i) ans=(ans+(ll)b[i]*L[i]*R[i])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}