GDOI2013 哈希和

Description

对于一个由小写字母组成的字符串s，我们定义：

1、s[i]表示字符串s的第i个字符，其中有1<=i<=len(s)

2、g(s[i])表示字符s[i]的ASCII码与字符‘a’的ASCII码的差值。

3、substr(i,j)表示由字符串s的第i个字母至第j个字母组成的一个连续子串，其中有1<=i<=j<=len(s)。

4、hash(i,j)表示substr(i,j)的哈希值，其中hash(i,j) =

现在给出一个由小写字母组成的字符串s，以及m个询问，每个询问给出两个整数x,y（x<=y），表示询问s的所有不同的连续子串中，字典序排名为x到y之间的所有字符串的哈希值的总和（包括x和y）。

Input

第一行一个由小写字母组成的字符串s，字符串的长度不会超过10^5.假设字符串s的不同连续子串的数目为t。

第二行有一个整数m（1<=m<=10^5），表示有m个询问。

接下来一共有m行，每行两个整数xi,yi(1<=xi<=yi<=t)，意义如题所述。

Output

对于每一组询问，输出一个整数，表示哈希和，由于数值可能很大，所以你只要输出答案模12580即可。

Sample Input

abcab

5

1 1

1 5

2 5

4 11

1 12

Sample Output

0

7106

7106

1657

3039

Data Constraint

对于20%的数据，n<=100,m<=100

对于40%的数据，n<=5000,m<=10^5

对于100%的数据，n<=10^5,m<=10^5

Hint

字符串abcab一共有12个不同的连续子串，这些子串按照字典序从小到大排列分别为a,ab,abc,abca,abcab,b,bc,bca,bcab,c,ca,cab。

先用SA求不同字串的个数。再预处理以第一位开头，第i位结尾的所有字串的哈希和，即前缀和

对于输入的x,y，先二分出它们在哪个后缀上，然后用类似前缀和相减的处理即可.

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
typedef long long ll;

int n,mn,x,i;
int co[100011],sa[100011],rank[100011],h[100011],nr[100011],sum[100011];
int a[100011],b[100011],ts[100011],hash[100011],suf[100011];
ll son[100011];
char s[100011];
char c;

void Read()
{
    while(c=getchar(),c<'a'||c>'z');
    s[++n]=c;
    while(c=getchar(),c>='a'&&c<='z')s[++n]=c;
}

void sort(int *a)
{
    int i;
    for(i=0;i<=mn;i++)co[i]=0;
    for(i=1;i<=n;i++)co[a[i]+1]++;
    for(i=1;i<=mn;i++)co[i]+=co[i-1];
    for(i=1;i<=n;i++)nr[i]=0;
    for(i=1;i<=n;i++){
        co[a[sa[i]]]++;
        nr[co[a[sa[i]]]]=sa[i];
    }
    for(i=1;i<=n;i++)sa[i]=nr[i];
}

void getrank()
{
    int i;
    x=0;
    for(i=1;i<=n;i++){
        if(i==1||a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]])x++;
        rank[sa[i]]=x;
    }
}

void Suffix()
{
    int i,j,k,l,last;
    if(27>n)mn=27;
    else mn=n;
    for(i=1;i<=n;i++){
        a[i]=s[i]-96;
        b[i]=0;
        sa[i]=i;
    }
    sort(a);
    getrank();
    l=1;
    while(x!=n){
        for(i=1;i<=n;i++){
            a[i]=rank[i];
            if(i+l<=n)b[i]=rank[i+l];
            else b[i]=0;
        }
        sort(b);
        sort(a);
        getrank();
        l*=2;
    }
    last=0;
    for(i=1;i<=n;i++){
        if(last)last--;
        if(rank[i]==1)continue;
        j=i;
        k=sa[rank[i]-1];
        while(j+last<=n&&k+last<=n&&s[j+last]==s[k+last])last++;
        h[rank[i]]=last;
    }
}

int ha(int st,int len)
{
    int z,ed;
    ed=st+len-1;
    z=((sum[ed]-sum[st-1])%12580+12580)%12580;
    z=((z-hash[st-1]*ts[len])%12580+12580)%12580;
    return z;
}

void Prepare()
{
    int j;
    j=1;
    for(i=1;i<=n;i++){
        son[i]=(ll)son[i-1]+n-sa[i]+1-h[i];
        hash[i]=(hash[i-1]*26+s[i]-97)%12580;
        sum[i]=(sum[i-1]+hash[i])%12580;
        j=(j*26)%12580;
        ts[i]=(ts[i-1]+j)%12580;
    }
    for(i=1;i<=n;i++){
        suf[i]=((suf[i-1]+ha(sa[i],n-sa[i]+1)-ha(sa[i],h[i]))%12580+12580)%12580;
    }
}

int find(ll x)
{
    int l,r,mid;
    l=1;
    r=n;
    while(l<=r){
        mid=(l+r)/2;
        if(son[mid]>=x)r=mid-1;
        else l=mid+1;
    }
    return l;
}

int Work()
{
    int i,m,q,xzq,j,xs,zs;
    ll xl,zl;
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        xl=0;
        zl=0;
        scanf("%lld%lld",&xl,&zl);
        xs=find(xl);
        zs=find(zl);
        if(zs-1>xs)xzq=((suf[zs-1]-suf[xs])%12580+12580)%12580;
        else xzq=0;
        xl=xl-son[xs-1];
        zl=zl-son[zs-1];
        if(xs!=zs){
            xzq=((xzq+ha(sa[xs],n-sa[xs]+1)-ha(sa[xs],h[xs]+xl-1))%12580+12580)%12580;
            xzq=((xzq+ha(sa[zs],h[zs]+zl)-ha(sa[zs],h[zs]))%12580+12580)%12580;
        }
        else{
            xzq=((xzq+ha(sa[xs],h[xs]+zl)-ha(sa[xs],h[xs]+xl-1))%12580+12580)%12580;
        }
        printf("%d
",xzq);
    }
}

int main()
{
    Read();
    Suffix();
    Prepare();
    Work();
}