5732. 促融共竞

单点时限: 2.0 sec

内存限制: 512 MB

给定一个长度为$n(1 \leq n \leq 10^5)$ 的字符串$s$,字符串下标从1开始。

给出 $m(1 \leq m \leq 10^5)$次询问,每次询问给定两个数$l,r (1\leq l \leq r \leq n)$,删除$s_ls_{l+1}…s_{r-1}s_r$后,得到的两个字符串$s_1s_2…s_{l-1}$和$s_{r+1}s_{r+2}…s_{n}$各自有多少种不同的回文子串。

输入格式

第一行,一个数$T(1 \leq T \leq 10^5)$。

每组数据第一行一个整数$n$,表达字符串长度。

第二行一个字符串$s$。

第三行一个整数$m$,表示询问次数。

接下来$m$行,每行两个整数$l,r$,表示要删除的子串左右端点。

数据保证$\sum n \leq 5\times 10^5, \sum m \leq 5 \times 10^5$

输出格式

对于每组数据,输出共$m$行,每行两个数,分别表示两个字符串$s_1s_2…s_{l-1}$和$s_{r+1}s_{r+2}…s_{n}$不同的回文子串种数。

样例

Input
3
3
cab
2
1 2
2 3
7
caccbcc
2
3 5
4 5
4
baca
2
1 2
3 3
Output
0 1
1 0
2 2
3 2
0 2
2 1

19 人解决,25 人已尝试。

19 份提交通过,共有 97 份提交。

5.2 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 4 月,1 周前.

来源: N/A

题目标签