#113705

Крыса - роботяга

Темы: [Дерево отрезков, RSQ, RMQ] [Хеш] [Бор] [Сканирующая прямая]

Компания « Rapid City Dynamics » знаменита её роботами-собаками, роботами-гепардами и даже человекоподобными роботами. Но большие проекты требуют больших денег, так что компания решила создать что-то простое, но популярное (и более востребованное). Так что компания разрабатывает нового робота « Rat-O-Matic », и вы, как работник « Rapid City Dynamics », принимаете участие в этом.

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

Есть ровно n рамок. Каждая рамка задана тремя числами: x , y и r . Она задаёт территорию, ограниченую между двух квадратов со сторонами параллельным осям координат и центрами в точке ( x , y ): радиус первого квадрата r , а второго — 2· r . Радиус квадрата — это расстояние между его центром и стороной. Ко всему прочему, каждой рамке соответствует своя нота. Сейчас есть только 3 возможных ноты, обозначим их как « r », « a » и « t ».

Гарантируется, что никакие две рамки не касаются и не пересекаются.

Вы можете взаимодействовать с роботом, вбивая номер рамки на специальной клавиатуре (рамки пронумерованы начиная с 1 ). Изначально, крыса находится снаружи всех рамок. Благодаря патентованной системе навигации, робот выбирает путь до рамки, который пересекает минимальное количество рамок. Когда крыса наступает на рамку в первый раз, соответствующая нота добавляется в мелодию. Робот останавливается после того, как наступит на нужную рамку.

Известно, что людям нравятся похожие мелодии. В вашей базе данных имеются m мелодий. Каждая мелодия задаётся строкой из символов, которая задаёт ноты. Мелодия, сгенерированная крысой, содержится в мелодии из базы данных, если она содержится в ней в качестве подстроки. Популярность сгенерированной мелодии - это число мелодий в базе данных, которые содержат её. Одинаковые мелодии из базы данных должны быть учтены несколько раз.

В попытке создания самого классного расположения рамок, вы совершили q экспериментов. Эксперименты бывают трёх типов:

Выключить рамку x . Гарантируется, что рамка была включена до этой операции. Выключенные рамки не влияют на мелодию крысы. Вначале все рамки включены.
Включить рамку x . Гарантируется, что рамка была выключена до этой операции.
Посчитать популярность мелодии, сгенерированной роботом при движении от точки с координатами ( 10 ⁹ , 10 ⁹ ) до рамки x . Гарантируется, что рамка x является включённой.

Твоя задача — провести эти эксперименты, используя только свой компьютер!

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

В первой строке содержится натуральное число n — количество рамок ( 1 ≤ n ≤ 2·10 ⁵ ).

В следующих n строках описаны рамки, i -я из них содержит три натуральных числа x _i , y _i , r _i и символ c _i , разделённые пробелами ( - 10 ⁸ ≤ x _i , y _i ≤ 10 ⁸ , 1 ≤ r _i ≤ 10 ⁸ , и c _i $\text{[math]}$ {« r », « a », « t »} — координаты центра рамки, радиус внутреннего квадрата и её нота, соответственно.

Следующая строка содержит натуральное число m — количество мелодий в базе ( 1 ≤ m ≤ 2·10 ⁵ ).

Следующие m строк содержат непустые строки из букв « r », « a » или « t », которые задают мелодии. Суммарная длина всех строк не превосходит 2·10 ⁵ .

Следующая строка содержит натуральное число q — количество экспериментов ( 1 ≤ q ≤ 2·10 ⁵ ).

Следующие q строк описывают эксперименты, j -я из них содержит символ t _j (« - », « + » или « ? ») и натуральное число x _j отделённое пробелом. Символ задаёт тип эксперимента (« - » — 1, « + » — 2 и « ? » — 3), а число обозначает номер рамки.

Гарантируется, что есть хотя бы один эксперимент третьего типа.

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

Для каждого эксперимента третьего типа, выведите одно число — популярность получившейся мелодии.

Группы тестов (Все группы независимы)

10 баллов — (1 ≤ n, m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 2-6) .

10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 7-9) .

10 баллов — ( 1 ≤ n, q ≤ 100, 1 ≤ m ≤ 200 000 , суммарная длина строк не превосходит 200 000, тесты 10-13) .

10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m ≤ 200 000, 1 ≤ q ≤ 100, суммарная длина строк не превосходит 200 000, тесты 14-16) .

10 баллов — ( 1 ≤ n ≤ 200 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 17-19) .

15 баллов — ( 1 ≤ n, q ≤ 200 000, 1 ≤ m ≤ 100, суммарная длина строк не превосходит 100, тесты 20-23) .

35 баллов — полные ограничения, тесты 24-57.

Примеры

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

3
3 3 4 r
2 4 1 a
14 4 1 t
3
rat
rara
aaa
6
? 3
? 2
- 1
? 2
+ 1
? 2

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

#113706

Почтовая реформа

Темы: [Деревья] [Дерево отрезков, RSQ, RMQ]

В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.

Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.

Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j .

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

Первая строка входного файла содержит число n — количество городов в Флатландии ( 1 ≤ n ≤ 50 000 ). Во второй строке находится n положительных чисел, не превосходящих 10 ⁵ — высоты башен в городах. В следующих n - 1 строках содержится по два числа u _i и v _i — описание i -й дороги, 1 ≤ u _i , v _i ≤ n , u _i ≠ v _i . В следующий строке содержится число k — количество запросов ( 1 ≤ k ≤ 100 000 ). В следующих k строках содержатся описания запросов в следующем формате:

Уведомление от волшебника из города i о том, что высота его башни стала равна h , имеет вид ! i h , 1 ≤ i ≤ n , 1 ≤ h ≤ 10 ⁵ .
Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j , 1 ≤ i , j ≤ n .

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

Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.

Группы тестов (Все группы независимы)

20 баллов — ( 1 ≤ n, k ≤ 100) .

30 баллов — каждый город соединен дорогами не более чем с двумя другими.

50 баллов — полные ограничения.

Примеры

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

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

3
3
5

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

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

1
1000

#113707

Симпатичные прямоугольники наносят ответный удар

Темы: [Хеш] ["Два указателя"]

Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc a

cb и a

Напишите программу, которая по информации о шедевре Васи определит его стоимость.

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

В первой строке содержатся два числа N и M ( 1 ≤ N , M ≤ 300 ). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i -й строке j -м столбце определяет цвет соответствующего квадратика картины.

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

Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.

Система оценки

n, m < 10 -> 20 баллов

n, m < 50 -> 30 баллов

n, m < 100 -> 20 баллов

n, m < 300 -> 30 баллов

Примечание

Этот пример разобран в условии

Симпатичными являются шесть частей 1 × 1 , одна часть 1 × 2 и сама картина.

Примеры

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

2 3
abc
acb

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

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

3 2
ab
cc
ba

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

#113774

Фурье?

Темы: [Быстрое преобразование Фурье] [Динамическое программирование: два параметра] [Корневая эвристика (sqrt декомпозиция)]

Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.

Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .

Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 ³ + 2 ³ + 1 ³ = 27 + 8 + 1 = 36 .

Поскольку задача должна быть интересной, вам нужно посчитать интересность всех чисел от 1 до n по модулю MOD .

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

В единственной строке входных данных задаются два числа n и MOD ( 1 ≤ n ≤ 10 ⁵ , 1 ≤ MOD ≤ 10 ⁹ + 7 ) — максимальное число, для которого надо посчитать интересность, и модуль.

Модуль не обязательно простой.

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

Выведите n строк, в i -й строке должна содержаться интересность числа i по модулю MOD .

Система оценки

Данная задача содержит 8 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.

1 ≤ n ≤ 5 , 5 баллов.
1 ≤ n ≤ 10 , 5 баллов.
1 ≤ n ≤ 20 , 10 баллов.
1 ≤ n ≤ 100 , 10 баллов.
1 ≤ n ≤ 1000 , 10 баллов.
1 ≤ n ≤ 5000 , 10 баллов.
1 ≤ n ≤ 50 000 , 25 баллов.
1 ≤ n ≤ 100 000 , 25 баллов.

Примеры

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

3 998244353

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

1
9
36

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

10 3

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

#113775

Все на выборы!

Темы: [Корневая эвристика (sqrt декомпозиция)] [Дерево Фенвика]

Ограничение по времени, сек	4
Ограничение по памяти, мегабайт	512

Я на выборы никогда не ходил, но в этот раз точно пойду за Зигги голосовать. Кандидат от народа!

Вдохновившись трудами греческих философов, Спортакус решил избрать главу правительства в Лентяево. Поскольку греческие философы убедили Спортакуса, что демократия является лучшим видом государственного устройства, он решил провести выборы. Для этого он открыл n избирательных участков, пронумерованных от 1 до n . Известно, что на участке с номером i проголосовали a _i жителей Лентяево.

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

Опишем действия Спортакуса более формально. Регионом с границами l и r Спортакус называет множество избиртельных участков, чьи номера лежат на промежутке от l до r включительно. k -й порядковой статистикой массива чисел супергерой называет число, которое бы находилось на k -й позиции в этом массиве, если бы он был упорядочен по возрастанию.

Стефани огорчает, что явка на выборах не соотетствует её ожиданиям, поэтому она решила слегка изменить значения явок на некоторых участках так, чтобы выборы казались более успешными. Для этого она выбирает четыре числа l , r , x и y и на всех избирательных участках региона с границами l и r , на которых явка равна x меняет протокол, после чего явка на этих участках становится равной y .

Напишите программу, отвечающую на запросы Спортакуса с учётом изменений, которые делает Стефани.

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

В первой строке содержатся два целых числа n и m ( 1 ≤ n , m ≤ 100 000 ) — количество избирательных участков и количество событий.

Во второй строке содержатся n целых чисел ( 1 ≤ a _i ≤ n ) — количество людей, проголосовавших на участке с номером i .

В следующих m строках содержатся описания событий. Каждое событие задано в одном из двух форматов.

1 l r x y ( 1 ≤ l ≤ r ≤ n , 1 ≤ x , y ≤ n ) обозначает, что Стефани на всех участках региона с границами l и r и явкой x установила явку равной y .

2 l r k ( 1 ≤ l ≤ r ≤ n , 1 ≤ k ≤ r - l + 1 ) обозначает, что Спортакуса интересует значение k -й порядковой статистики явок на участках в регионе с границами l и r .

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

Для каждого вопроса Спортакуса выведите ответ на него.

Система оценки

Группа 1 (10 баллов) 1 ≤ n , m ≤ 100 . Для прохождения этой подгруппы требуется прохождение тестов из условия.

Группа 2 (10 баллов) 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение тестов из условия.

Группа 3 (10 баллов) 1 ≤ n , m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение группы 2.

Группа 4 (20 баллов) 1 ≤ n , m ≤ 100 000 , в запросах первого типа l = r . Для прохождения этой подгруппы требуется прохождение группы 3.

Группа 5 (50 баллов) Без дополнительных ограничений. Для прохождения этой подгруппы требуется прохождение всех предыдущих групп.

Примеры

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

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

2
1