4131. [USACO25 Open Bronze]It s Mooin Time III

【题目描述】

Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛，但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说 ⌈现在是哞哞时间！谁想哞哞？拜托，我只想参加 USACO⌋。

Bessie 仍然不理解，于是她将 Elsie 的描述转文字得到了一个长为 $N \; (3\leq N\leq10^5)$ 的字符串，包含小写字母字符 $s_1s_2\dots s_N$。Elsie 认为一个包含三个字符的字符串 $t$ 是一个哞叫当且仅当 $t_2=t_3$ 且 $t_2\ne t_1$。

一个三元组 $(i,j,k)$ 是合法的，如果 $i\lt j\lt k$ 且字符串 $s_is_js_k$ 组成一个哞叫。对于该三元组，FJ 执行以下操作计算其值：

• FJ 将字符串 $s$ 在索引 $j$ 处弯折 $90$ 度。
• 该三元组的值是 $\triangle ijk$ 的面积的两倍。

换句话说，该三元组的值等于 $(j-i)(k-j)$。

Bessie 向你进行 $Q \; (1\leq Q\leq 3\times10^4)$ 次询问。在每次询问时，她给你两个整数 $l$ 和 $r \; (1\leq l\leq r\leq N, \; r-l+1\geq 3)$，并询问满足 $l\leq i$ 和 $k\leq r$ 的所有合法三元组 $(i,j,k)$ 的最大值。如果不存在合法的三元组，输出 $-1$。

注意这个问题涉及到的整数可能需要使用 64 位整数类型（例如，C/C++ 中的 "long long"）。

大样例

【输入格式】

输入的第一行包含两个整数 $N$ 和 $Q$。

以下一行包含 $s_1s_2\dots s_N$。

以下 $Q$ 行，每行包含两个整数 $l$ 和 $r$，表示每个查询。

【输出格式】

对于每一个查询输出一行，包含对于该查询的答案。

【样例输入】

12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10

【样例输出】

28
6
1
-1
12

【样例说明】

• 对于第一个查询，$(i, j, k)$ 必须满足 $1 \leq i \lt j \lt k \leq 12$。可以证明，对于某个合法的 $(i, j, k)$，$\triangle ijk$ 的最大面积在 $i = 1$，$j = 8$ 以及 $k = 12$ 时取到。注意 $s_1s_8s_{12}$ 是字符串 "acc"，根据前述定义是一个哞叫。$\triangle ijk$ 的直角边长为 7 和 4，从而它的面积的两倍将等于 28。
• 对于第三个查询，$(i, j, k)$ 必须满足 $4 \leq i \lt j \lt k \leq 8$。可以证明，对于某个合法的 $(i, j, k)$，$\triangle ijk$ 的最大面积在 $i = 4$，$j = 5$ 以及 $k = 6$ 时取到。
• 对于第四个查询，不存在满足 $2 \leq i \lt j \lt k \leq 5$ 的 $(i, j, k)$ 使得 $s_is_js_k$ 是一个哞叫，所以该查询的输出为 $-1$。

【数据规模与约定】

【来源】

USACO 2025 US Open Contest, Bronze