Задача №113572. Трезвый Доминик
Хан не хотел учиться один, поэтому он пригласил своего друга Доминика позаниматься вместе с ним. После того, как они решили рекордное количество задач за вечер, Доминик поехал домой. Внезапно его остановила полиция, подозревая, что он водил в пьяном виде. Чтобы проверить Доминика, полицейские начали задавать ему вопросы.
Полицейский: Давайте начнём с чего-то простого. Какова асимптотика сортировки пузырьком?
Доминик: О, это просто. O ( n 2 ) .
Полицейский: Скажите английский алфавит наоборот.
Доминик: Легко, zyxwvutsrqponmlkjihgfedcba.
Полицейский: Вы просто запомнили это. Представьте, что строчные буквы латинского алфавита записаны по кругу по часовой стрелке. Начинайте с буквы 'a' и называйте все буквы подряд. После каждой сказанной буквы я могу приказать теперь называть в обратном порядке, спросить сколько раз была названа какая-то буква или ничего не делать. Приступайте.
Доминик: Хм... a, b, c...
Возможно, Доминик не настолько трезв, чтобы решить эту задачу. Помогите ему.
Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) – количество приказов полицейского. Каждая из последующих Q строк содержит один из приказов в формате "SMJER n" или "UPIT n x". Приказ первого типа обозначает, что после n -й сказанной буквы требуется поменять направление. Приказ второго типа обозначает, что Доминик должен сказать, сколько раз он произнес букву x после n сказанных букв.
Во всех запросах 1 ≤ n ≤ 10 9 , а x – строчные латинские буквы. В запросах n идут в строго возрастающем порядке.
Для каждого запроса вида "UPIT n x", выведите ответ на этот запрос, каждый в отдельной строке, в том же порядке, что и в вводе.
40 баллов: n ≤ 1000
60 баллов: n ≤ 10 5
100 баллов: n ≤ 10 9
В первом примере Доминик говорит a, b, c, d, c, b, a, z, y, x.
Во втором примере Доминик говорит a, z, a, z, y, x, w.
5 UPIT 1 b UPIT 3 b SMJER 4 UPIT 7 a UPIT 10 z
0 1 2 1
5 SMJER 1 SMJER 2 SMJER 3 UPIT 5 a UPIT 7 w
2 1
4 UPIT 100 a UPIT 200 c UPIT 300 a UPIT 400 b
4 8 12 16