首先马拉车一遍（或者用hash），再做个前缀和处理出f[i][j]表示以j为右端点，左端点在[i,j]的回文串个数
然后设ans[i][j]是[i,j]之间的回文串个数，那就有ans[i][j]=ans[i][j-1]+f[i][j]
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int rad[maxn<<],N,Q,ans[maxn][maxn];
int f[maxn][maxn];
char s[maxn<<]; int main(){
int i,j,k;
scanf("%s",s+);N=strlen(s+);
for(i=N;i;i--){
s[i<<]=s[i];s[i<<|]='#';
}s[]='#',s[]='!';
int a=,p=;
for(i=;i<=(N<<|);i++){
rad[i]=p>=i?min(p-i+,rad[*a-i]):;
while(s[i+rad[i]]==s[i-rad[i]]) rad[i]++;
if(i+rad[i]->p) p=i+rad[i]-,a=i;
for(j=;j<=rad[i];j++){
if(s[i+j-]!='#') f[(i-j+)>>][(i+j-)>>]=;
}
}
for(i=;i<=N;i++){
for(j=i;j;j--) f[j][i]+=f[j+][i];
}
for(i=;i<=N;i++){
for(j=i;j<=N;j++){
ans[i][j]=ans[i][j-]+f[i][j];
}
}
Q=rd();
for(i=;i<=Q;i++){
int a=rd(),b=rd();
printf("%d\n",ans[a][b]);
}
return ;
}