题意翻译
题目描述
给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。
输入格式
第1行，给出s，s的长度小于5000 第2行给出q(1<=q<=10^6) 第2至2+q行 给出每组询问的l和r
输出格式
输出每组询问所问的数量。
题目描述
You've got a string s=(s_{1})(s_{2})...(s_{|s|}) of length |s| , consisting of lowercase English letters. There also are qq queries, each query is described by two integers (l_{i}),(r_{i}) (1<=(l_{i})<=(r_{i})<=|s|) . The answer to the query is the number of substrings of string (s[) (l_{i}) ... (r_{i}) (]) , which are palindromes.
String (s[l... r])=(s_{l})(s_{l+1})...( s_{r})(1<=l<=r<=∣s∣) is a substring of string (s=s_{1}s_{2}... s_{|s|}) .
String tt is called a palindrome, if it reads the same from left to right and from right to left. Formally, if (t=t_{1}t_{2}... t_{|t|}=t_{|t|}t_{|t|-1}... t_{1}).
输入输出格式
输入格式：
The first line contains string ss (1<=|s|<=5000) . The second line contains a single integer qq (1<=q<=106) — the number of queries. Next qq lines contain the queries. The ii -th of these lines contains two space-separated integers (l_{i}),(r_{i}) (1<=(l_{i})<=(r_{i})<=|s|) — the description of the i-th query.
It is guaranteed that the given string consists only of lowercase English letters.
输出格式：
Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.
输入输出样例
输入样例#1： 复制
caaaba
5
1 1
1 4
2 3
4 6
4 5
输出样例#1： 复制
1
7
3
4
2
说明
Consider the fourth query in the first test case. String (s[4... 6]) = «aba». Its palindrome substrings are: «a», «b», «a», «aba».
题解
这个题目的思路非常巧妙？
因为时间复杂度允许达到(n)2,于是我们就从1开始一直到strlen(s)，(l)的位置每向后移动一位就清空回文树，并把这个(l...len)的回文串重新放入回文树。用(ans[l][r])来统计一下答案
然后o(1)查询就OK了。
然后我yy了一下莫队？
是不是离线的话时间复杂度就降到了(n{sqrt n})了呢？
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int fail,len,ch[26],dep;
}t[5001];
int tot,k,ans[5001][5001];
char s[5001],ch[5001];
int read()
{
int x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
void clear()
{
memset(t,0,sizeof(t));
tot=1;k=0;t[0].fail=t[1].fail=1;t[1].len=-1;
}
void solve()
{
int n=strlen(ch+1);
for(int i=1;i<=n;i++)
{
clear();
for(int j=i;j<=n;j++)s[j-i+1]=ch[j];
for(int j=i;j<=n;j++)
{
//clear();
while(s[j-i+1-t[k].len-1]!=s[j-i+1])k=t[k].fail;
if(!t[k].ch[s[j-i+1]-'a']){
t[++tot].len=t[k].len+2;
int l=t[k].fail;
while(s[j-i+1-t[l].len-1]!=s[j-i+1])l=t[l].fail;
t[tot].fail=t[l].ch[s[j-i+1]-'a'];
t[k].ch[s[j-i+1]-'a']=tot;
t[tot].dep=t[t[tot].fail].dep+1;
}
k=t[k].ch[s[j-i+1]-'a'];
ans[i][j]=ans[i][j-1]+t[k].dep;
}
}
}
int main()
{
scanf("%s",ch+1);
solve();
int q=read();
for(int i=1;i<=q;i++)
{
int l=read(),r=read();
printf("%d
",ans[l][r]);
}
return 0;
}