Запросы на различные символы (усложнённая версия)

Вам задана строка s, состоящая из строчных букв латинского алфавита и q запросов к этой строке.

Напомним, что подстрокой s[l;r] строки s называется строка slsl+1…sr. Например, подстроками «codeforces» являются «code», «force», «f», «for», но не строки «coder» и «top».

Всего существует два вида запросов:
1 l r - заменить каждую букву на отрезке s[l;r] на следующую. (Идущую за ней в алфавитном порядке. Например: буква 'a' должна замениться за 'b', буква 'f' на 'g', а буква 'z' на 'a'.)
2 l r - посчитать количество различных символов в подстроке s[l;r].
Входные данные
Первая строка входных данных содержит одну строку s, состоящую из не более, чем 10^5 строчных букв латинского алфавита.

Вторая строка входных данных содержит одно целое число q (1≤q≤10^5) — количество запросов.

Следующие q строк содержат запросы, по одному в строке. Каждый запрос задан в формате, описанном в условии задачи. Гарантируется, что есть хотя бы один запрос второго типа.

Выходные данные
На каждый запрос второго типа выведите ответ на него — количество различных символов в подстроке, заданной в этом запросе.

Пример
Входные данные
codeforces
4
1 4 6
2 1 6
1 4 4
2 1 6
Выходные данные
6
5

Ссылка на простую похожую версию https://codeforces.com/problem... bile=false

Подскажите, пожалуйста, оптимизированное решение данное задачи. Понимаю, что это похоже на дерево отрезков на массовые операции, но нет идей, как это реализовывать.

0