BZPRO
#5036. [Jsoi2014]回文串
内存限制：256 MiB
时间限制：30 Sec
提交
提交记录
讨论
题目描述
JYY又重新切换到计算机科学家状态并幵始研宄回文串啦！不过呢，很长的回文串对脑袋不太够用的JYY来说有点棘
手，所以请你帮忙。JYY现在有一个由小写字母组成的字符串S。我们用S[i,j]表示S中从第i个字符到第j个字符所
组成的子串(字符串下标从1开始)。现在JYY有Q个询问，其中第i个询问(Li,Ri)需要统计满足如下条件的子串S[x,y
]的数量：
1、 Li ≤ x ≤ y ≤ Ri。
2、 S[x,y]是回文串。
请你帮助JYY计算这Q个询问的答案。
输入格式
第一行包含一个字符串S;
第二行包含一个正整数Q;
接下来Q行，每行两个整数Li和Ri。
对于所有数据满足：1≤|S|≤10^5 & 1≤Q≤3*10^5 & 1≤Li≤Ri≤|S|
输出格式
输出包含Q行，每行个一个整数，第i行的整数为第i个询问的答案。
样例
样例输入
abaa
4
1 2
1 3
1 4
3 4
样例输出
2
4
6
3
数据范围与提示
BZPRO