21/11/2024 21:12:32

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2622. Удаление буквы

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Рассмотрим строку ``ABBC``.
Удаляя из неё ровно одну букву, можно получить следующие *различные* строки ``ABB``, ``ABC`` и ``BBC``.

Дана строка `S`. Найдите количество *различных* строк, которые можно получить из части
строки `S` с `i`-го по `j`-й символ включительно.

Первая строка ввода содержит непустую строку `S` (`2 <= |S| <= 10^6`),
состоящую из прописных латинских букв.
Вторая строка ввода содержит одно целое число `N` (`1 <= N <= 10^4`) - количество запросов.
Далее следует `N` строк, каждая строка содержит два целых числа `i` и `j` (`1 <= i < j <= |S|`).

Для каждого запроса вывести одно целое число на отдельной строке -- количество *различных* строк, которые можно получить из части
строки `S` с `i`-го по `j`-й символ включительно.

```sample Пример ввода
ABBCCC
3
1 4
4 6
1 2
```

```sample Пример вывода
3
1
2
```