Древовидные структуры данных

На шахматном турнире участники получают баллы. Судья хочет в любой момент знать: какой максимальный и какой минимальный балл среди всех участников?

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

+ X — игрок с баллом X пришёл на турнир

- X — игрок с баллом X ушёл с турнира

? — запрос минимального и максимального балла

Формат входных данных

В первой строке — число Q (1 ≤ Q ≤ 100000) — количество событий.

В следующих Q строках — события в указанном формате.

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

Формат выходных данных

Для каждого запроса "?" выведите два числа через пробел: минимальный и максимальный балл.

Сайтама выполняет последовательные удары по силомеру. Силомер представляет из себя массив целых чисел длины \(n\). Изначально \(i\)-е число массива равно \(a_i\) для всех \(i\).

Вам необходимо обработать \(q\) событий, происходящих с силомером. Событие номер \(i\) может быть одного из трех типов:

1. подходит наблюдатель и просит посчитать сумму чисел массива на отрезке \([l_i; r_i]\), то есть величину \(a_{l_i} + a_{{l_i}+1} + \ldots + a_{r_i}\);

2. Сайтама наносит обычный удар силы \(x_i\) по отрезку \([l_i; r_i]\): всем элементам массива на позициях от \(l_i\) до \(r_i\) включительно присваивается значение \(x_i\)

3. Сайтама наносит сильный удар по отрезку \([l_i; r_i]\): для всех \(j\) от \(l_i\) до \(r_i\) включительно происходит присваивание \(a_j \gets \mathtt{popcount}(a_j)\).

Здесь \(\mathtt{popcount}(x)\) — это количество единичных бит в двоичной записи числа \(x\). Иными словами, при событии третьего типа каждое число на отрезке события заменяется на количество своих единичных бит.

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

Формат входных данных
В первой строке записаны два целых числа \(n\) и \(q\) — длина массива и количество событий (\(1 \leqslant n, q \leq 2 \cdot 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел \(a_1\), …, \(a_n\) — изначальные элементы массива силомера (\(0 \leqslant a_i \leqslant 10^9\)).

Следующие \(q\) строк описывают события. Первое число \(t_i\) в описании события — тип события (\(1 \leqslant t \leqslant 3\)). Следующие два заданные через пробел числа — это границы отрезка \(l_i\) и \(r_i\) (\(1 \leqslant l_i \leqslant r_i \leqslant n\)). Если это событие второго типа, то есть \(t_i = 2\), далее следует число \(x_i\), обозначающее, что надо выполнить присваивания \(a_j \gets x_i\) для всех \(l_i \leqslant j \leqslant r_i\) (\(0 \leqslant x_i \leqslant 10^9\)).

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

 

Для сборки лаборатории-поселения на Венеру доставлены \(n\) блоков. Блоки расположены в ряд, \(i\)-й блок имеет высоту \(h_i\).

Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться.

Исходно каждый блок представляет собой отдельный сегмент, сегменты пронумерованы от \(1\) до \(n\) в том же порядке, что и блоки. Если есть два соседних сегмента, составленных из блоков: сегмент из блоков \(A = [i, i+1, \ldots, i+p-1]\) и сегмент из блоков \(B = [i+p, i+p+1, \ldots, i+p+q-1]\), то после их объединения в один получается сегмент \(AB = [i, i+1, \ldots, i+p-1, i+p, i+p+1, \ldots, i+p+q-1]\).

Инструкция по сборке состоит из \(n-1\) инструкций. Каждая инструкция характеризуется одним числом, \(j\)-я инструкция характеризуется числом \(k_j\). После выполнения этой инструкции сегменты с номерами \(k_j\) и \(k_j + 1\) объединяются в один, получившийся сегмент занимает место в последовательности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах в том порядке, в котором они расположены — номера сегментов, начиная с \(k_j + 2\), уменьшаются на один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент.

На Венере постоянно идут кислотные дожди, поэтому в процессе сборки важно для каждого сегмента блоков понимать, сколько жидкости может скопиться в этом сегменте. Пусть сегмент состоит из блоков высотой \(h_l, h_{l+1}, \ldots, h_r\). Для \(p\), где \(l \le p \le r\) определим глубину блока c высотой \(h_p\) в этом сегменте следующим образом. Посчитаем величины \(l_p = \max \{ h_l, \ldots, h_p \}\), \(r_p = \max \{ h_p, \ldots, h_r\}\). Это самые высокие блоки в сегменте слева и справа от \(p\)-го. Тогда глубина блока \(p\) в его сегменте равна \(d_p = \min(l_p, r_p) - h_p\), заметим, что \(d_p \ge 0\). Емкостью сегмента будем называть сумму глубин блоков этого сегмента, то есть \(w = d_l + d_{l+1} + \ldots + d_r\).

Задана последовательность объединений сегментов. После каждого объединения выведите емкость получившегося сегмента.

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

Формат входных данных
Первая строка содержит одно целое число \(n\) — количество блоков (\(2 \leq n \leq 10^5\)).

Во второй строке записано \(n\) чисел \(h_1, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)).

В третьей строке записаны \(n - 1\) чисел — инструкции по объединению сегментов. Каждая инструкция характеризуется одним числом \(k_j\) (\(1 \leq k_j \leq n - j\)).

Формат выходных данных
Выведите \(n-1\) чисел — после каждого объединения сегментов выведите емкость получившегося объединенного сегмента.

Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов \(\frac{n(n+1)}{2}\). Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.

С фонарями регулярно происходят события одного из двух типов:

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

Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события.

Входные данные
В первой строке входных данных содержатся два числа \(n\) и \(q\) — количество фонарей и количество произошедших событий. Следующая строка входных данных состоит из \(n\) символов 0 и 1, описывающих начальное состояние фонарей, где 1 обозначает фонарь с исправной лампочкой, а 0 — с перегоревшей.

В каждой из последующих \(q\) строк содержатся описания событий в виде трёх чисел \(l_i, r_i\) и \(c_i\), которые означают, что после этого события все лампочки в фонарях с номерами \(l_i, l_i+1, \ldots, r_i\):

В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение \(0\) или \(1\).

Выходные данные
В первой строке выходных данных выведите единственное число "— количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите \(q\) чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.

Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1<W<10⁹) и бесконечной высоты. В этот стакан падают сверху N фигурок (1<N<100000). i-я фигурка представляет собой прямоугольник шириной в W_i клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1<a_i<W–W_i+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.

В отличие от обычного тетриса, игрок не имеет возможности вращать фигурки или смещать их по горизонтали в процессе падения — еще бы, это пришлось бы делать быстро и не было бы времени серьёзно подумать над стратегией. Единственное, что он может — это выбрать порядок, в котором эти N фигурок упадут в стакан (каждая по одному разу). Ваша задача — помочь ему выбрать такой порядок, при котором высота образовавшейся в результате падения конструкции была бы как можно меньше. (В отличие от обычного тетриса, полностью заполненная фигурками горизонталь никуда не исчезает).

На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).



Входные данные
В первой строке записаны числа N и W, а в последующих N строках — пары чисел a_i и W_i.

Выходные данные
Выведите минимальную возможную высоту конструкции, а затем последовательность номеров фигурок, к этой высоте приводящую. Фигурки нумеруются натуральными числами от 1 до N в том порядке, в котором они указаны во входных данных. Если возможных вариантов несколько, выведите любой из них.

Первая сессия обычно доставляет много проблем. Одна из них заключается в том, что студенту нужен по крайней мере целый день, чтобы подготовиться к одному экзамену. В день одного экзамена к другому готовиться невозможно. Но основная проблема заключается в том, что студенты могут начать готовиться к i-му экзамену, не раньше чем за t_i дней до него, иначе они все забудут. Глеб хочет начать готовиться к экзаменам как можно позже, но он собирается все экзамены сдать.

Помогите Глебу выбрать день начала подготовки к экзаменам.

Входные данные
Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину t_i для этого экзамена (1 ≤ t_i ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.

Выходные данные
Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.

Ценные бумаги на фондовом рынке характеризуются множеством параметров. У них есть цена и ликвидность, также оценивать динамичность изменения цены, среднюю прибыльность, потенциал роста прибыльности и др. показатели. Аналитики трейдовой компании "WebMarket" ввели специальный показатель надежности ценной бумаги и научились эффективно его оценивать. Большое значение этого показателя соответствует малому риску покупки ценной бумаги. Но с ростом надежности обычно падает среднее оцениваемое значение прибыльности.

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

Ценные бумаги в базе данных имеют три атрибута:

• code — непустая строка латинских символов и цифр длины 30 или меньше
• id — целочисленный идентификатор (начиная с 0)
• reliability — целое число из диапазона [−2³¹,2³¹)

.
Каждой новой ЦБ выдается следующий по порядку id и значение её надёжности устанавливается в 0. Если ценная бумага отзывается с рынка, ее id для новых бумаг не используется.

База данных получает запросы, которые позволяют вводить новые ЦБ на рынок, получать текущую информацию о ЦБ, отзывать ЦБ с рынка, менять значение надежности у ЦБ и находить ЦБ, которая стоит на n-м месте, если упорядочить ЦБ по убыванию надежности, а при одинаковых значениях по возрастанию идентификатора.

При добавлении ЦБ с кодом, который раньше встречался, но соответствующая ЦБ была отозвана с рынка, ей назначается новый идентификатор.

Входные данные
Первая строка входа содержит число запросов N. (1≤N≤100000). Затем идут N  строк, каждая из которых содержит один запрос. Запросы бывают 4 типов:

• ISSUE code: добавить новую ЦБ code в базу данных, или вывести информацию о ЦБ, если она уже есть в базе
  • если ЦБ code существует, то вывести EXISTS id reliability
  • если ЦБ code не существует, то вывести CREATED id 0
• DELETE code: удалить ЦБ code из базы
  • если ЦБ code существует, то вывести OK id reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• RELIABILITY code reliability: увеличить количество очков ЦБ, гарантируется, что значение останется в диапазоне [−2³¹,2³¹)
  • если ЦБ code существует, то вывести OK id new_reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• FIND n: найти n-ю ЦБ (начиная с 0)
  • если база не пуста, найти ЦБ, которая имела бы порядковый номер n (нумерация начинается с 0), если все ЦБ упорядочить сначала по убыванию баллов, а группы ЦБ с одинаковыми баллами упорядочить по времени их добавления (то есть по возрастанию id); а если n больше, чем количество ЦБ в базе, то найти последнюю ЦБ в этом порядке; для обоих случаев вывести OK code id reliability
• если база пуста, то вывести EMPTY

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

Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа t обозначим h(t) максимальное значение k, такое что t делится на 2k. Например, h(24)=3, h(5)=0. Обозначим l(t)=2h(t), например, l(24)=8, l(5)=1.

Рассмотрим массив a[1], a[2], … , a[n] целых чисел. Дерево Фенвика для этого массива — это массив b[1], b[2], …, b[n], такой что  \( \sum\limits_{j=i-l(i)+1}^{i}a[j] \) Таким образом: b[1]=a[l], b[2]=a[l]+a[2], b[3]=a[3], b[4]=a[l]+a[2]+a[3]+a[4], b[5]=a[5], b[6]=a[5]+a[6], Например, дерево Фенвика для массива a=(3,−1,4,1,−5,9) есть массив b=(3,2,4,7,−5,4).

Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив a=(0,−1,1,1,0,9) таковым является.

Вам дан массив а. Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.

Входные данные
В первой строке входных данных содержится количество чисел в массиве n (1 ≤ n ≤ 100000). Во второй строке находятся сами n целых чисел. Все числа по модулю не превосходят 10⁹.

Выходные данные
Выведите n чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.

В холле 179 школы, есть информационный стенд размером H×W (H – высота, W – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.

Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.

Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером 1×W_i.

Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).

Входные данные
Первая строка содержит три целых числа H, W и N (1≤H,W≤10⁹; 1≤N≤200000) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу W_i (1≤W_i≤10⁹) — ширину i-го объявления.

Выходные данные
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от 1 до H сверху вниз. Если объявление разместить нельзя — выведите «–1».

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤  N ≤  150000, 1 ≤ K ≤ 10000, K ≤  N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.

Отсортируйте данный массив. Используйте пирамидальную сортировку.

Входные данные
Первая строка входных данных содержит количество элементов в массиве N,  N  ≤  10⁵. Далее задаются N целых чисел, не превосходящих по абсолютной величине 10⁹.

Выходные данные
Выведите эти числа в порядке неубывания.

Отрезок целочисленной прямой длины N разбит на единичные отрезки, которые пронумерованы от 1 до N.

Их объединяют в группы по следующим правилам:
1. Несколько подряд идущих отрезков, ни один из которых не принадлежит ни одной из групп, могут быть объединены в группу.
2. Любая ранее созданная группа может быть уничтожена, при этом входившие в нее отрезки больше не относятся ни к какой группе и могут впоследствии быть отнесены к другим группам.

Видно, что любой отрезок всегда находится не более, чем в одной группе.

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

Первоначально нет ни одной группы.

Входные данные
Первая строка входных данных содержит число N – количество отрезков и число K – количество запросов (1 ≤ N, K ≤10⁵). Далее идет K строчек, содержащих запросы к структуре данных. Каждый запрос начинается с числа 1 (запрос на создание группы) или 2 (запрос на удаление группы). После числа 1 указывается два других числа l и r (1 ≤ l ≤ r ≤ N), после числа 2 указывается одно число i (1 ≤ i ≤ N).

Выходные данные
Для каждого запроса типа 1 необходимо отрезки с номерами от l до r объединить в группу. Если все эти отрезки не входят ни в одну группу, запрос считается удачным и программа должна вывести 1. Если хотя бы один из этих отрезков уже относится к какой-то группе, запрос считается неудачным, объединение не производится и программа выводит 0.

Для каждого запроса типа 2 необходимо удалить группу, в которую входит отрезок с номером i, при этом программа должна вывести два числа: номер первого и последнего отрезка, входящих в удаляемую группу. Если отрезок с номером i не относится ни к одной группе, программа должна вывести два нуля.

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

Входные данные
В первой строке вводится натуральное число N (1 ≤  N ≤ 10⁵) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 10⁹ – элементы массива. Далее идет число K  (0 ≤ K ≤ 10⁵) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ N) – левую и правую границы отрезка в массиве для данного запроса.

Выходные данные
Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от l до r и индекс одного из элементов массива, принадлежащий отрезку от l до r, на котором достигается этот максимум.

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

Входные данные
Первая строка входных данных содержит число N (2 ≤ N ≤ 10⁵). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из n городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до n, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог T, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора T из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из T во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

Входные данные
В первой строке входного файла записана пара целых чисел n и m (2 ≤ n≤ 4000; n−1 ≤ m ≤100000), где n — количество городов в стране, а m— количество дорог в этой стране. Далее в m строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел a_j, b_j, l_j, t_j , где a_j, b_j это номера городов, соединяемых дорогой (1 ≤ a_j,b_j ≤ n; a_j≠b_j), l_j — ее длина (1 ≤ l_j≤ 10⁵), а t_j равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор T удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

Выходные данные
Выведите n−1 число в строку через пробелы. i-ое число должно быть равно либо длине кратчайшго пути из столицы в город i+1, при условии, что по той дороге из T, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города i+1 вообще невозможно.