C++14(g++5.4) 解法, 执行用时: 2191ms, 内存消耗: 3100K, 提交时间: 2018-07-08 15:04:21

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
const int N=3e4+5;
typedef long long ll;
const ll mod=1e9+7,u=131;
ll getHash(int *num) {
    ll ans=0;for(int i=0;i<26;i++) ans=(ans*u+num[i])%mod;
    return ans;
}
std::map<ll,int> f;
int q,n,k,num[26],block;ll has[N],ans[N];char s[N];
struct Query {
    int l,r,id;
    bool operator < (const Query &b) const {
        if(l/block!=b.l/block) return l/block<b.l/block;
        return r<b.r;
    }
}Q[N];
int main() {
    scanf("%d%s",&k,s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++) ++num[s[i]-'a'],num[s[i]-'a']%=k,has[i]=getHash(num);
    scanf("%d",&q);int l,r;
    for(int i=1;i<=q;i++) {
        scanf("%d%d",&l,&r);
        Q[i]=(Query){l,r,i};
    }
    block=int(sqrt(n));
    std::sort(Q+1,Q+1+q);int ql,qr;l=1,r=0;ll now=0;f[0]=1;
    for(int i=1;i<=q;i++) {
        ql=Q[i].l,qr=Q[i].r;
        while(r<qr) ++r,now+=f[has[r]],f[has[r]]++;
        while(l>ql) --l,now+=f[has[l-1]],f[has[l-1]]++;
        while(r>qr) --f[has[r]],now-=f[has[r]],r--;
        while(l<ql) --f[has[l-1]],now-=f[has[l-1]],l++;
        ans[Q[i].id]=now;
    }
    for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1100ms, 内存消耗: 6436K, 提交时间: 2018-07-11 18:39:03

#include<bits/stdc++.h>
using namespace std;
int k,q;string s;
typedef unsigned long long ull;
const int N=3e4+10;int blo;
struct node{int l,r,id;}qq[N];
int sum[N][26];ull aa[N];
int ans[N],p_[N];
map<ull,int>mp;int now;
bool cmp1(node a,node b){
	if(a.l/blo!=b.l/blo) return a.l<b.l;
	return a.r<b.r;
}
void work(int u,int v){
	if(v==1) now+=mp[aa[u]]++;
	else now-=--mp[aa[u]];
}
int main(){
	std::ios::sync_with_stdio(false); 
	cin>>k>>s>>q;int x,y;s='0'+s;
	int len=s.size()-1;
	for(int i=1;i<=q;i++){cin>>qq[i].l>>qq[i].r;qq[i].l--;qq[i].id=i;}
	blo=sqrt(len);
	sort(qq+1,qq+q+1,cmp1);
	for(int i=1;i<=len;i++){
		for(int j=0;j<26;j++) sum[i][j]=sum[i-1][j];
		sum[i][s[i]-'a']=(sum[i][s[i]-'a']+1)%k;
	} 
	for(int i=1;i<=len;i++) {
        ull pt=0;
        for(int j=0;j<26;++j) pt=pt*233+sum[i][j];
        aa[i]=pt;
    }
    int l,r;l=r=qq[1].l;mp[aa[l]]++; 
	for(int i=1;i<=q;i++){
		while(l<qq[i].l) work(l++,-1);
		while(r>qq[i].r) work(r--,-1);
		while(l>qq[i].l) work(--l,1);
		while(r<qq[i].r) work(++r,1);
		ans[qq[i].id]=now;	
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
	return 0;
}