分数: 1200 点
问题陈述
对于字符串 X = X_1X_2\dots X_{|X|} 和正整数 l,r~(1 \leq l \leq r \leq |X|),让 X_{l,r} = X_l X_{l+1}\dots X_r.
给你一个字符串 S=S_1S_2\dots S_{|S|} 组成 A 和 B.
你被给予 Q 查询。对于每个查询,回答以下问题:
- 从状态开始 T = S_{l,r},找到通过执行操作“选择一次出现的回文”可以获得的最小可能长度
AB作为连续子字符串出现在 T 并将其删除”零次或多次。
如果无论如何运算都无法得到回文数,则输出-1.
约束
- 1 \leq |S| \leq 4 \times 10^5
- 1 \leq Q \leq 5 \times 10^4
- 1 \leq l \leq r \leq |S|
- S 是一个由以下组成的字符串
A和B. - Q,l,r 是整数。
输入
输入由标准输入按以下格式给出:
S
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
\mathrm{Query}_q 代表 q-第一个查询,以以下格式给出:
l r
输出
输出 Q 行。的 q- 第行应包含以下问题的答案 \mathrm{Query}_q.
示例输入 1
ABBABB 5 1 6 4 5 3 5 2 3 3 4
示例输出 1
2 0 1 2 -1
对于第一、第二、第三个查询,通过如下操作,可以得到该操作得到的回文中长度最小的回文。
ABBABB\rightarrowABBB\rightarrowBBAB\rightarrow (空字符串)BAB\rightarrowB