- Описание
- Отправленные решения
257. RLE-сжатие
RLE-сжатие — один из самых простых методов сжатия строки, основанный на сокращении подстрок, состоящих из одинаковых символов. Сжатие осуществляется следующим образом:
- Строка разбивается на минимальное количество подстрок, состоящих из одинаковых символов. Например,
abbcaaa
превращается в строкиa
,bb
,c
,aaa
. - Каждая из полученных строк превращается в строку, состоящую из числа и буквы. Числом является количество повторений символа в этой строке, буква берётся из первого символа обрабатываемой строки. Число не добавляется, если количество символов в строке равно единице. Из предыдущего массива строк мы получаем
a
,2b
,c
,3a
. - Затем полученные строки конкатенируются в исходном порядке. В рассмотренном примере в итоге получим
a2bc3a
.
Вам дана строка $s$, уже сжатая в $RLE$-формате. Назовём строку, из которой была получена $s$, строкой $t$. Вам даны $q$ запросов, каждый из них представлен целыми числами $l$ и $r$. В каждом запросе вам необходимо найти длину сжатой
подстроки $t[l \ldots r]$.
Формат ввода
В первой строке входного файла записана строка $s$, состоящая из строчных букв латинского алфавита и цифр $(1 \le |s| \le 1\,000\,000)$. Гарантируется, что существует такая непустая строка $t$, из которой $RLE$-сжатием получается строка $s$. Также гарантируется, что в строке $t$ не было больше $1\,000\,000\,000$ одинаковых подряд идущих символов.
В следующей строке дано количество запросов $q$ $(1 \le q \le 100\,000)$. Каждая из следующих $q$ строк содержит два числа $l_i$ и $r_i$ $(1 \le l_i \le r_i \le |t|)$ — параметры запросов.
Формат вывода
Выведите $q$ чисел, каждое в отдельной строке — ответы на запросы в том порядке, в котором запросы были заданы во входных данных.
Ограничения
Ограничение времени
1 с
Ограничение памяти
512 МБ
Пример 1
a2bc3a
5
1 7
5 7
1 2
3 5
4 4
6
2
2
3
1
Пример 2
x1000000000yz
3
2 1000000001
2 1000000002
5938493 15938493
11
12
9