$O(s^2)$ 预处理数量后用莫队完成查询，复杂度 $O( s^2 + q \sqrt s)$ ，过了样例，CF提交MLE求调。

#include<bits/stdc++.h>
using namespace std;
int h[5010][5010];
int rt[5010][5010],lt[5010][5010],m;
char a[5010],sq;
void inti()
{
   for(int i=0;i<strlen(a);i++)
   {
   	int l=i,r=i;
   	while(a[l]==a[r]&&l>=0&&r<strlen(a))
   		h[l][r]=1,l--,r++;
   	l=i,r=i+1;
   	while(a[l]==a[r]&&l>=0&&r<strlen(a))
   		h[l][r]=1,l--,r++;
   }
   for(int i=0;i<strlen(a);i++)
   {
   	lt[i][0]=1;
   	for(int j=1;i+j<strlen(a);j++)
   		lt[i][j]=lt[i][j-1]+h[i][i+j];
   }
   for(int i=strlen(a)-1;i>=0;i--)
   {
   	rt[i][0]=1;
   	for(int j=1;i-j>=0;j++)
   		rt[i][j]=rt[i][j-1]+h[i-j][i];
   }
   return ;
}
struct query{
   int l,r;
   int id,ans;
}q[1000010];
bool cmp1(query A,query B)
{
   if(A.l/sq==B.l/sq)
   {
   	return A.r<B.r;
   }
   else
   {
   	return A.l>B.l;
   }
}
bool cmp2(query A,query B)
{
   return A.id<B.id;
}
int main()
{
   scanf("%s",a);
   inti();
   scanf("%d",&m);
   sq=(strlen(a)/sqrt(m));
   for(int i=1;i<=m;i++)
   {
   	scanf("%d%d",&q[i].l,&q[i].r);
   	q[i].l-=1,q[i].r-=1;
   	q[i].id=i;
   }
   sort(q+1,q+m+1,cmp1);
   int L=0,R=0,ans=1;//此时存在回文 a[0]
   for(int i=1;i<=m;i++)
   {
   	while(R>q[i].r)
   	{
   		ans-=rt[R][R-L];
   		R--;
   	}
   	while(L>q[i].l)
   	{
   		L--;
   		ans+=lt[L][R-L];
   	}
               while(R<q[i].r)
               {
                       R++;
                       ans+=rt[R][R-L];
               }

   	while(L<q[i].l)
   	{
   		ans-=lt[L][R-L];
   		L++;
   	}
   q[i].ans=ans;
   }
   sort(q+1,q+m+1,cmp2);
   for(int i=1;i<=m;i++)
   	cout<<q[i].ans<<'\n';
   return 0;
}