P5112 FZOUTSY

传送门

没想到这题还这能用莫队……本来看看以为复杂度会挂的……

预处理出每个字母开头往后\(k\)个的字符串的哈希值，然后大概就是那道小z的袜子了

而且据说这题的哈希得用自然溢出

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll unsigned long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

const int N=3e6+5,Base=233;

int n,m,cnt[N],rt[N],k,q,S,l,r,tot;char s[N];ll bin[N],a[N],b[N],sum[N],ans[N],res;

struct node{

	int l,r,id;

	inline bool operator <(const node &b)const

	{return rt[l]==rt[b.l]?rt[l]&1?r<b.r:r>b.r:l<b.l;}

}qq[100005];

inline void add(R int x){res+=cnt[a[x]],++cnt[a[x]];}

inline void del(R int x){--cnt[a[x]],res-=cnt[a[x]];}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d%d%d",&n,&q,&k),S=n/sqrt(q);if(S==0)S=1;

	scanf("%s",s+1);

	bin[0]=1;fp(i,1,n)bin[i]=bin[i-1]*Base,sum[i]=sum[i-1]*Base+s[i]-'a',rt[i]=(i-1)/S+1;

	n=n-k+1;

	fp(i,1,n)b[i]=a[i]=sum[i+k-1]-bin[k]*sum[i-1];

	sort(b+1,b+1+n),m=unique(b+1,b+1+n)-b-1;

	fp(i,1,n)a[i]=lower_bound(b+1,b+1+m,a[i])-b;

	fp(i,1,q){

		scanf("%d%d",&l,&r);

		if(l<=n){

			if(r>n)r=n;

			++tot,qq[tot].l=l,qq[tot].r=r,qq[tot].id=i;

		}

	}sort(qq+1,qq+1+tot);

	res=0,l=1,r=0;

	fp(i,1,tot){

		while(l>qq[i].l)add(--l);

		while(r<qq[i].r)add(++r);

		while(l<qq[i].l)del(l++);

		while(r>qq[i].r)del(r--);

		ans[qq[i].id]=res;

	}fp(i,1,q)printf("%lld\n",ans[i]);return 0;

}