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

Планируется строительство новой магистрали <<Урал>>. Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

Под будущей магистралью залегают \(n\) горизонтальных пластов. Геологическое исследование позволило определить точки магистрали, под которыми начинается и заканчивается каждый из них. При этом порядок залегания пластов по глубине определить не удалось.

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

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

Формат входных данных
Первая строка входного файла содержит целое число \(n\) "— количество пластов. Пласты пронумерованы целыми числами от \(1\) до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (\(0 \leqslant l_i < r_i\leqslant 10^9\)) "— расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) "— количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (\(0 \leqslant x \leqslant 10^9\)) и \(k\) (\(0 \leqslant k \leqslant n\)) "— расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем "— целые числа \(s_1, s_2, \ldots, s_k\) "— номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходных данных
Первая строка выходного файла должна содержать \(n\) целых чисел \(p_1, p_2, \ldots , p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1, p_2, \ldots , p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1, \ldots ,p_{j-1}\) или ниже пластов с номерами \(p_{j+1}, \ldots , p_n\).

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

Примечание
Рисунок в условии соответствует примеру. Для приведенного примера правильным также является ответ 2 3 1 4. Обратите внимание, что тест из примера не соответствует подзадаче 1. Для того, чтобы решение было принято на проверку, оно должно проходить тест из примера, даже если решена только эта подзадача.

План студенческого городка некоторого университета представляет собой квадрат \(n \times n\), в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.

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

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата \(A_{i,j}\) планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат \(A_{i,j}\). Количество таких автоматов на этом пути называется избыточностью автомата \(A_{i,j}\). При этом автомат \(A_{1,1}\) находится в общежитии, а автомат \(A_{n,n}\) — в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от \(1\) до \(2n - 1\) определяет число автоматов с таким значением избыточности.

Формат входных данных
Первая строка содержит целое число \(n\) (\(2 \leqslant n \leqslant 1500\)). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате \(A_{i,j}\). Номера продуктов находятся в диапазоне от \(1\) до \(n^2\).

Формат выходных данных
Строка должна содержать \((2n-1)\) целых чисел — количество автоматов с избыточностями \(1, 2, \ldots, 2n - 1\) соответственно.

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

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.

Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:

• \(1\) \(i\) \(x\) —  запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));

• \(2\) \(m\) \(l\) \(r\) —  запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).

Формат выходных данных
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. В случае если для отрезка не существует никакого \(m\)-разбиения, выведите \(0\).

В задаче присутствуют 6 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Есть шарики, пронумерованные от \(1\) до \(n\). Также поступают \(q\) запросов:

• \(add\) \(x\) - добавить в дек шарик с номером \(x\). Вы можете положить шарик либо сверху, либо снизу дека.

• \(del\) \(x\) - удалить из дека шарик с номером \(x\). Вы находите шарик с номером \(x\) в деке, достаете все шарики НИЖЕ \(x\), удаляете шарик \(x\), потом кладете достанные шарики (без \(x\)) обратно в том же порядке.

На запросы \(1\)-го типа вы тратите \(1\) действие, а на запросы \(2\)-го типа - \(2k + 1\) действий, где \(k\) - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете \(k\) шариков, потом удаляете нижний, потом кладете достанные \(k\) шариков обратно в том же порядке).

Посчитайте, какое минимальное количество действий вы можете потратить.

Формат входных данных
Первая строка содержит числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10^5\)) - максимальный номер шарика и количество запросов. Далее следуют \(q\) строк в формате:

• \(add\) \(x\) - добавить шарик с номером \(x\) (\(1 \leq x \leq n\)) в начало или конец дека.

• \(del\) \(x\) - удалить шарик с номером \(x\) (\(1 \leq x \leq n\)) из дека.

Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика \(x\), то он присутствует в деке в данный момент.

Формат выходных данных
Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.

Замечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

Формат входных данных
В первой строке входных данных находится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массива Васи.

Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива.

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).

Разберем подробнее первый пример.

1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).

2. \(b_2=c_{2,2,4}\).

3. \(b_3=c_{3,3,5}\).

4. \(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).

5. \(b_5=c_{5,1,5}\).

Примеры

Примеры

Примеры

Примеры