--->
10 задач
<---
Источники
Капрал Питуца любит командовать своим отрядом. Его любимый приказ «в начало строя». Он выстраивает свой отряд в шеренгу и оглашает последовательность приказов. Каждая приказ имеет вид «Солдаты с \(l_i\) по \(r_i\) — в начало строя!»
Пронумеруем солдат в начальном положении с 1 до \(n\), слева направо. Приказ «Солдаты с \(l_i\) по \(r_i\) — в начало строя!» означает, что солдаты, стоящие с \(l_i\) по \(r_i\) включительно, перемещаются в начало строя, сохраняя относительный порядок.
Например, если в некоторый момент солдаты стоят в порядке \(2, 3, 6, 1, 5, 4\), после приказа: «Солдаты с \(2\) по \(4\) — в начало строя!» порядок будет \(3, 6, 1, 2, 5, 4\).
По данной последовательности приказов найти конечный порядок солдат в строю.
В первой строке два целых числа \(n\) and \(m\) (\(2 \le n \le 100\,000\), \(1 \le m \le 100\,000\)) — количество солдат и количество приказов. Следующие \(m\) строк содержат по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).
Выведите \(n\) целых чисел — порядок солдат в конечном положении после выполнения всех приказов.
6 3 2 4 3 5 2 2
1 4 5 2 3 6
Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.
Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).
Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.
3 1 2 2 3 3 1 2 1 1 2 2
0 0 2 0 0
Маленький мальчик Глеб еще толком не познал жизнь, но он уже ОЧЕНЬ любит КАРАТЬ, НЕ ПРОЩАТЬ! И вот в очередной раз он решил поиздеваться над бедным Лёшиком =(
Он сказал, что у него есть первая четверть плоскости, он умеет добавлять на нее прямоугольник с нижней левой точкой (0;0) и верхней правой (x;y), умеет считать площадь получившейся фигуры, умеет считать площадь объединения этой фигуры с прямоугольником на точках (x1;y1) и (x2;y2) и даже площадь пересечения.
Лёшик в печальке... =(
Спасите Лёшика, решите эту задачу. Но помните, Глеб настолько суров, что заставил решать поставленную задачу в он-лайне!!!
В первой строке задано число N (1 ≤ N ≤ 105). Далее следует описание запросов:
первое число t — тип запроса
t = 0: вводятся числа x и y, значит нужно добавить прямоугольник с координатами (0;0) и (x;y)
t = 1: вы должны вывести площадь получившейся фигуры
t = 2: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь пересечения фигуры и такого прямоугольника
t = 3: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь объединения фигуры и такого прямоугольника
Так как Глеб коварен, то все числа в запросах нужно еще преобразовать. Пусть ANS — ответ на предыдущий запрос. Изначально ANS = 0.
Тогда при t = 0 x = 1 + (x + ANS): mod: 109, y = 1 + (y + ANS): mod: 109.
При t = [2, 3] x1 = 1 + (x1 + ANS): mod: (5·108), y1 = 1 + (y1 + ANS): mod: (5·108), x2 = x1 + 1 + (x2 + ANS): mod: (5·108), y2 = y1 + 1 + (y2 + ANS): mod: (5·108).
После запросов типа 1, 2 или 3 ANS = ответу на этот запрос.
Выведите ответы на запросы.
В 1 примере даны запросы, которые не преобразуются по заданным формулам для простоты понимания.
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24
Физики проводят эксперимент для исследования частиц трёх типов: \(x\), \(y\) и \(z\). Они запускают в коллайдер пронумерованный ряд из \(n\) частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с \(i\)-ого места ряда и моментально появляется на месте \(j\). После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте \(k\). Напишите программу, которая поможет физикам.
В первой строке файла два целых числа: \(n\) – количество частиц и m — общее количество воздействий и вопросов (1 \(\le\) \(n\) \(\le\) 1000000, 1 \(\le\) \(m\) \(\le\) 15000). Во второй строке — последовательность из символов \(x\), \(y\) и \(z\) длиной \(n\). На каждой из следующих \(m\) строк (1 \(\le\) \( m\) \(\le\) 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом \(a\) и после пробела дается два целых числа из интервала [1; \(n\)]. Первое из них показывает начальное, а второе конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом \(q\) и после пробела дается одно целое число из интервала [1; \(n\)]. Оно указывает позицию, которая интересует физиков.
Выведите столько строк, сколько вопросов во входном файле. В строке номер \(i\) надо записать ответ на вопрос \(i\) — название соответствующей частицы \(x\), \(y\) или \(z\).
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,
15 6 xzxyyzxxzxyyzyx a 2 10 a 15 4 q 3 a 12 2 q 14 q 2
y z y
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
начала вводятся размеры поля N и M ( 1 ≤ N ≤ 20 , 1 ≤ M ≤ 50000 ), затем количество команд K ( 1 ≤ K ≤ 10 5 ), а затем сами команды. Команды записаны по одной в строке в следующем формате:
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0 , если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.
5 5 10 Neighbors 3 1 Color 4 1 Color 2 4 Color 4 5 Color 2 2 Neighbors 5 4 Neighbors 5 5 Neighbors 2 4 Color 3 5 Neighbors 3 5
3 2 1 4 1 3 2 3 4 4 5 3 5 5 2 3 5 5 4 4 1 4 3 4 2 3 2 5 3 2 5 5 5 3 4