3277. 【GDOI2013】哈希和 (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB
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）。
现在给出一个由小写字母组成的字符串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#include #include #include #include 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\n",xzq); }}int main(){ Read(); Suffix(); Prepare(); Work();}