Задача №115122. Вася и Петя
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Друзья Вася Л. и Петя П. — талантливые мальчики, которые любят писать песни собственного сочинения. В будущем они хотят стать популярными музыкантами. Ребята знают: чтобы добиться успеха, нужно регулярно тренироваться. Именно поэтому они каждый день пишут по новой песне, совершенствуя свое мастерство.
Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(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\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.
В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку «aba», которая превратится в «abba», а значит, ответ на этот вопрос равен 4. Во втором вопросе Вася рассматривает подстроку «baca», которая превратится в «bbaccca», а значит, ответ на этот вопрос будет равен 7. В третьем вопросе Вася рассматривает всю строку «abacaba», которая превратится в «abbacccabba» — строку длины 11.
Для получение номера буквы можно использовать следующий код:
-
В языке python3 или pypy3 выражение
ord(x) - 96
, например
ord('a') - 96
равно 1, а
ord('x') - 96
равно 24.
-
В языке c++ выражение
x - 96
, например
'a' - 96
равно 1, а
'x' - 96
равно 24.
- В языке pascal выражение ord(x) - 96 , например ord('a') - 96 равно 1, а ord('x') - 96 равно 24.
В данной задаче \(20\) тестов, помимо тестов из условия, каждый из них оценивается в \(5\) баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n, q \le 1000\), наберут не менее \(25\) баллов.
Решения, корректно работающие при \(n, q \le 10\,000\), наберут не менее \(50\) баллов.
Решения, корректно работающие в случае, когда \(s\) состоит из символов \(a,b\), наберут не менее \(25\) баллов.
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