这么写会 TLE：

#include<bits/stdc++.h>
using namespace std;
int n,p,m,siz,pos[100005],cnt[100005],a[100005],b[100005],po,len,l=1,r;
long long ans[100005],res;
char ch[100005];
struct node
{
	int l,r,id;
	bool operator<(const node &t) const{return pos[l]!=pos[t.l]?l<t.l:r<t.r;}
}c[100005];
inline void add(int u){res-=1ll*cnt[u]*(cnt[u]-1)/2,++cnt[u],res+=1ll*cnt[u]*(cnt[u]-1)/2;}
inline void del(int u){res-=1ll*cnt[u]*(cnt[u]-1)/2,--cnt[u],res+=1ll*cnt[u]*(cnt[u]-1)/2;}
inline void sol()
{
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&c[i].l,&c[i].r),c[i].id=i,++c[i].r;
	sort(c+1,c+m+1); 
	siz=sqrt(n),po=1,pos[n+1]=n/siz+1;
	for(int i=n;i;--i) b[i]=a[i]=(1ll*(ch[i]-'0')%p*po%p+a[i+1])%p,pos[i]=(i-1)/siz+1,po=1ll*po*10%p;
	sort(b+1,b+n+2),len=unique(b+1,b+n+2)-b-1;
	for(int i=1;i<=n+1;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	for(int i=1;i<=m;++i)
	{
		while(l<c[i].l) del(a[l++]);
		while(l>c[i].l) add(a[--l]);
		while(r<c[i].r) add(a[++r]);
		while(r>c[i].r) del(a[r--]);
		ans[c[i].id]=res;
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}
inline void solu()
{
	for(int i=1;i<=n;++i) pos[i]=pos[i-1]+((ch[i]-'0')%p==0?i:0),cnt[i]=cnt[i-1]+((ch[i]-'0')%p==0?1:0);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&l,&r),printf("%d\n",pos[r]-pos[l-1]-(cnt[r]-cnt[l-1])*(l-1));
}
int main()
{
	scanf("%d%s",&p,ch+1),n=strlen(ch+1);
	if(p^2&&p^5) sol();
	else solu();
	return 0;
}

将输入询问+排序询问放在后面，就可以 AC：

#include<bits/stdc++.h>
using namespace std;
int n,p,m,siz,pos[100005],cnt[100005],a[100005],b[100005],po,len,l=1,r;
long long ans[100005],res;
char ch[100005];
struct node
{
	int l,r,id;
	bool operator<(const node &t) const{return pos[l]!=pos[t.l]?l<t.l:r<t.r;}
}c[100005];
inline void add(int u){res-=1ll*cnt[u]*(cnt[u]-1)/2,++cnt[u],res+=1ll*cnt[u]*(cnt[u]-1)/2;}
inline void del(int u){res-=1ll*cnt[u]*(cnt[u]-1)/2,--cnt[u],res+=1ll*cnt[u]*(cnt[u]-1)/2;}
inline void sol()
{
	siz=sqrt(n),po=1,pos[n+1]=n/siz+1;
	for(int i=n;i;--i) b[i]=a[i]=(1ll*(ch[i]-'0')%p*po%p+a[i+1])%p,pos[i]=(i-1)/siz+1,po=1ll*po*10%p;
	sort(b+1,b+n+2),len=unique(b+1,b+n+2)-b-1;
	for(int i=1;i<=n+1;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&c[i].l,&c[i].r),c[i].id=i,++c[i].r;
	sort(c+1,c+m+1); 
	for(int i=1;i<=m;++i)
	{
		while(l<c[i].l) del(a[l++]);
		while(l>c[i].l) add(a[--l]);
		while(r<c[i].r) add(a[++r]);
		while(r>c[i].r) del(a[r--]);
		ans[c[i].id]=res;
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}
inline void solu()
{
	for(int i=1;i<=n;++i) pos[i]=pos[i-1]+((ch[i]-'0')%p==0?i:0),cnt[i]=cnt[i-1]+((ch[i]-'0')%p==0?1:0);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&l,&r),printf("%d\n",pos[r]-pos[l-1]-(cnt[r]-cnt[l-1])*(l-1));
}
int main()
{
	scanf("%d%s",&p,ch+1),n=strlen(ch+1);
	if(p^2&&p^5) sol();
	else solu();
	return 0;
}

求助，为啥前者会 TLE，后者就不会，而且貌似时间差的还挺多的。