自己写的哈希56pts,自然溢出78pts,原来我完全不会哈希

#include<bits/stdc++.h> 
#define ri register int
#define ll unsigned long long
#define ld long double
#define int unsigned long long
using namespace std;
const int maxn=3e6+7,mod=100000073;
int n,m,k;
string tmp;
char s[maxn];
unsigned __int128 hashe[maxn];
unsigned __int128 a[maxn];
unsigned __int128 gsm[maxn];
ll get_ha(int l,int len){
	return hashe[l+len-1]-hashe[l-1]*gsm[len];
}
int siz;
struct query{
	int l,r;int id;
	bool operator < (const query &x) const{
		if(l/siz!=x.l/siz)return l<x.l;
		if((l/siz)&1)return r<x.r;
		return r>x.r;
	}
}que[maxn];
ll ans[maxn];
int nowl,nowr;
int sum[maxn];
ll cnt;
void add(int x){
	cnt+=1ll*sum[x]; 
	sum[x]++;
}
void del(int x){
	sum[x]--;
	cnt-=1ll*sum[x];
}
const int inf=1e9;
unsigned __int128 b[maxn];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	siz=sqrt(n);
	cin>>tmp;
	for(ri i=1;i<=n;i++)s[i]=tmp[i-1];
	for(ri i=1;i<=n;i++)hashe[i]=hashe[i-1]*233+s[i]-'a';
	gsm[0]=1;
	for(ri i=1;i<=k;i++)gsm[i]=gsm[i-1]*233;
	for(ri i=1;i<=n-k+1;i++){
		a[i]=get_ha(i,k);
	}
//	for(ri i=1;i<=n-k+1;i++){
//		cout<<a[i]<<' ';
//	}cout<<endl;
	for(ri i=1;i<=n-k+1;i++){
		b[i]=a[i];
	}
	sort(b+1,b+1+n-k+1);
	for(ri i=1;i<=n-k+1;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	for(ri i=1;i<=m;i++){
		int l,r;cin>>l>>r;
		if(l>r||l>n-k+1)ans[i]=0,que[i].l=inf;
		else if(r>n-k+1)que[i]=(query){l,n-k+1,i};
		else que[i]=(query){l,r,i};
	}
	sort(que+1,que+1+m);
	nowl=1,nowr=0;
	for(ri i=1;i<=m;i++){
		if(que[i].l==inf)break;
		int l=que[i].l,r=que[i].r;
		while(nowl<l){
			del(a[nowl]);
			nowl++;
		}
		while(nowl>l){
			nowl--;
			add(a[nowl]);
		}
		while(nowr<r){
			nowr++;
			add(a[nowr]);
		}
		while(nowr>r){
			del(a[nowr]);
			nowr--;
		}
		ans[que[i].id]=cnt;
	}
	for(ri i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}
/*
3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
*/