当前没有测试数据。

题目描述

给定一个长度为 $n$ 的小写字母字符串 $s$。

对于字符串中的一个区间 $[l,r]$，考虑所有满足 $l \le x \le y \le r$ 且 $s_x s_{x+1}\cdots s_y$ 为回文串的二元组 $(x,y)$。定义该区间的回文权为这些回文子串长度之和：

$$\sum_{\substack{l\le x\le y\le r\\s[x..y]\text{为回文串}}} (y-x+1)$$

位置不同的两个子串即使内容相同，也分别计算贡献。

给出 $q$ 个区间询问，请求出每个区间的回文权。

输入格式

第一行一个长度为 $n$ 的小写字母字符串 $s$。

第二行一个正整数 $q$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

对每次询问输出一行一个整数，表示区间 $[l,r]$ 的回文权。

样例

abacaba
4
1 7
2 6
3 5
4 4

28
13
6
1

样例解释 在区间 $[1,7]$ 中，长度为 $1$ 的回文子串贡献 $7$；三个长度为 $3$ 的回文子串贡献 $9$；$\text{bacab}$ 贡献 $5$；$\text{abacaba}$ 贡献 $7$，总和为 $28$。

数据规模与约定

• $1 \le n,q \le 2\times 10^5$；
• $s$ 仅包含小写英文字母；
• $1 \le l \le r \le n$；

共 $20$ 个测试点，每个测试点 $5$ 分。下表各行所列测试点共同满足对应的额外约束。

测试点编号	分值	额外约束
$1\sim 2$	$10$	$n,q \le 200$
$3\sim 4$		$n,q \le 2000$
$5\sim 6$		$s$ 中所有字符相同
$7\sim 8$		$s$ 不含长度大于 $1$ 的回文子串
$9\sim 10$		所有询问均为 $[1,n]$
$11\sim 13$	$15$	$\sum (r-l+1) \le 10^7$
$14\sim 16$		$s_i \neq s_{i+1}$ 对所有 $1\le i < n$ 成立
$17\sim 20$	$20$	无额外约束

原题链接

原题链接