e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

ADA University - March 7 - Segment Tree

На палубе пираты

В древние века землю населяли две команды пиратов: Буканеры и Бербэри. Число пиратов в командах не было фиксированным, иногда противники нападали друг на друга и превращали пленных в членов своей команды. Однажды в пиратской земле появился волшебник, который начал совершать переход пиратов из одной команды в другую по собственному желанию. Для этого были использованы необходимые заклинания. Процесс смены команды назывался мутацией.

Всего имеется n пиратов, каждый из которых имеет уникальный идентификационный номер id от 0 до n - 1. Великий маг может видоизменять набор пиратов с последовательными идентификационными номерами на другой.

Пусть на земле имеются 100 пиратов, и все они являются Бербэри пиратами. Маг совершает заклинание, которое изменяет пиратов с id от 10 до 33 на Буканеров. Теперь во всей земле имеются 24 Буканеров и 76 Бербэри пиратов.

Волшебник начал слишком быстро выполнять заклинания. Однажды Богу не понравилось это. Бог был милостив к Буканерам и спросил волшебника "Скажи мне, сколько пиратов с индексами от 2 до 30 являются Буканерами?". Теперь маг был озадачен, поскольку он был эффективен только в заклинаниях, но не в подсчете :-).

Будучи достаточно умным, маг захватил умного человека из планеты Земля. К сожалению, это были Вы! Теперь Вы должны ответить на вопросы Богов.

Входные данные

Первая строка содержит количество тестов t. Структура каждого теста следующая:

Первая часть входных данных описывает пиратскую землю. Она содержит до n (1n1024000) пиратов. Каждый пират принадлежит или команде Буканеров или Бербэри. Буканеры пираты обозначаются '1' (ОДИН), а Бербэри пираты обозначаются '0' (НОЛЬ). Вам следует построить строку пиратов из входных данных. Каждый тест начинается числом m (m100), за которым следует m пар строк. В каждой паре строк (будем называть ее набором), первая содержит целое число t (t200), а вторая - непустую строку пиратов (состоящую из 0 и 1, 0 - Бербэри, 1 - Буканеры, ее длина не более 50). Совершите конкатенацию этой строки с собой t раз. Теперь сконкатенируйте результирующие m наборов строк и получите строку - описание пиратов. Финальное объединение строк описывает пиратов начиная с индекса 0 и до конца (индекс n - 1 для n-го пирата).

Следующая часть входных данных содержит вопросы. Первая строка єтой части содержит количество вопросов q. Каждая из следующих q (1q1000) строк содержит один вопрос. Каждый вопрос начинается одной из букв F, E, I или S, за которой следуют два целых числа - индексы a и b. Значение этих запросов следующее:

F a b означает мутировать пиратов с индексами от a до b в Буканер пиратов.

E a b означает мутировать пиратов с индексами от a до b в Бербэри пиратов.

I a b означает мутировать пиратов с индексами от a до b в инвертированных пиратов.

S a b означает "вопрос Бога", Бог задает вопрос: "Скажи мне сколько Буканеров находится среди пиратов с индексами от a до b?"

(ab, 0a < n, 0b < n, границы диапазона включительно)

Выходные данные

Для каждого теста вывести его номер. Для каждого вопроса Бога вывести в отдельной строке его номер, двоеточие (:), пробел и ответ на вопрос.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
2
2
5
10
2
1000
5
F 0 17
I 0 5
S 1 10
E 4 9
S 2 10
3
3
1
4
0
2
0
2
I 0 2
S 0 8
Çıxış verilənləri #1
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0