← 返回题目列表

AtCoder · agc074_e

E. 删除AB

中文机器翻译题面 查看原题

分数: 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 \rightarrow ABBB \rightarrow BB
  • AB \rightarrow (空字符串)
  • BAB \rightarrow B