19 人解决,25 人已尝试。
19 份提交通过,共有 97 份提交。
5.2 EMB 奖励。
单点时限: 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}$不同的回文子串种数。
3 3 cab 2 1 2 2 3 7 caccbcc 2 3 5 4 5 4 baca 2 1 2 3 3
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