AT_agc074_e.[AGC074E] Delete AB

对于一个字符串 $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$。

给定一个仅由 A 和 B 组成的字符串 $S = S_1S_2\dots S_{|S|}$。
你需要回答 $Q$ 个查询。对于每个查询，回答如下问题：

• 从状态 $T = S_{l,r}$ 开始，可以进行多次如下操作：“选择 $T$ 中出现的一处连续的 AB 并将其删除”。最终可以得到若干不同的字符串。
  问通过若干步操作后，能够得到的回文字符串的最小可能长度是多少？如果无论如何操作都无法得到回文字符串，输出 $-1$。

输入从标准输入读入，格式如下：

$S$
$Q$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\vdots$
$\mathrm{Query}_Q$

其中 $\mathrm{Query}_q$ 表示第 $q$ 个查询，格式如下：

$l \ r$

输出共 $Q$ 行，第 $q$ 行输出对于 $\mathrm{Query}_q$ 的答案。

样例解释 1

对于第 1、2、3 个查询，进行如下操作可以得到最小长度的回文串：

• ABBABB $\rightarrow$ ABBB $\rightarrow$ BB
• AB $\rightarrow$ （空字符串）
• BAB $\rightarrow$ B

数据范围

• $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$ 均为整数。

由 ChatGPT 5 翻译