← 返回题目列表

Codeforces · 1555/D

D. 对回文说不

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

如果该字符串不包含长度至少为 $$$2$$$ 的子字符串(回文),我们称该字符串为“漂亮”。回文是一个字符串,从第一个字符到最后一个字符以及从最后一个字符到第一个字符的读取方式相同。例如,字符串 a、bab、acca、bcabcbacb 是回文,但字符串 ab、abbbaa、cccb 不是回文。

让我们将字符串的成本定义为使字符串变得漂亮的最少操作次数,如果在一次操作中允许将字符串的任何字符更改为拉丁字母表的前 $$$3$$$ 字母之一(小写)。

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串的每个字符都是拉丁字母表中前 $$$3$$$ 字母之一(小写)。

您必须回答 $$$m$$$ 查询 - 计算字符串 $$$s$$$ 的子字符串从第 $$$l_i$$$ 位置到第 $$$r_i$$$ 位置(含)的成本。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度和查询次数。

第二行包含字符串$$$s$$$,它由$$$n$$$个字符组成,每个字符是前$$$3$$$拉丁字母之一。

以下 $$$m$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 查询的参数。

输出

对于每个查询,打印一个整数 - 字符串 $$$s$$$ 从第 $$$l_i$$$ 位置到第 $$$r_i$$$ 位置(含)的子字符串的成本。

示例

输入 #1

5 4
baacb
1 3
1 5
4 5
2 3

输出 #1

1
2
0
1

注意

考虑示例测试的查询。

- 在第一个查询中,子字符串是 baa,可以通过一次操作将其更改为 bac;
- 第二次查询中,子字符串是baacb,可以通过两次操作将其更改为cbacb;
- 第三次查询中,子字符串为cb,可以保持不变;
- 在第四个查询中,子字符串是aa,可以通过一次操作将其更改为ba。