Codeforces Round 727 (Div. 2) |
---|
Закончено |
Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло $$$q$$$ вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции $$$l$$$ до позиции $$$r$$$. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке $$$k$$$ раз, где $$$k$$$ — порядковый номер буквы в алфавите. Например, если Вася выбрал подстроку «abbcb», то он повторит букву «a» один раз, каждую из букв «b» — по два раза, букву «c» — три раза, и полученная строка будет равна «abbbbcccbb», ее длина равна $$$10$$$. Вася интересуется именно длиной полученной строки.
Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.
В первой строке вводятся числа $$$n$$$ и $$$q$$$ ($$$1\leq n\leq 100\,000$$$, $$$1\leq q \leq 100\,000$$$) — длина песни и количество вопросов.
Во второй строке дана строка $$$s$$$ — сама песня, представляющая собой строку длины $$$n$$$ из маленьких букв английского алфавита.
В следующих $$$q$$$ строках даны описания вопросов. Каждое описание состоит из двух чисел $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — границы каждого из вопросов.
Выведите $$$q$$$ строк — для каждого вопроса выведите длину строки, которую выпишет Вася.
7 3 abacaba 1 3 2 5 1 7
4 7 11
7 4 abbabaa 1 3 5 7 6 6 2 4
5 4 1 5
13 7 sonoshikumiwo 1 5 2 10 7 7 1 13 4 8 2 5 3 9
82 125 9 191 62 63 97
В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку «aba», которая превратится в «abba», а значит, ответ на этот вопрос равен $$$4$$$. Во втором вопросе Вася рассматривает подстроку «baca», которая превратится в «bbaccca», а значит, ответ на этот вопрос будет равен $$$7$$$. В третьем вопросе Вася рассматривает всю строку «abacaba», которая превратится в «abbacccabba» — строку длины $$$11$$$.
Название |
---|