Задача A. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

Формат входного файла

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Формат выходного файла

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача B. Переворачивания ≡

Условие

Учитель физкультуры школы с углубленным изучением предметов уже давно научился считать суммарный рост всех учеников, находящихся в ряду на позициях от l до r. Но дети играют с ним злую шутку. В некоторый момент дети на позициях с l по r меняются местами. Учитель заметил, что у детей не очень богатая фантазия, поэтому они всегда "переворачивают" этот отрезок, т. е. l меняется с r, l + 1 меняется с r − 1 и так далее. Но учитель решил не ругать детей за их хулиганство, а все равно посчитать суммарный рост на всех запланированных отрезках.

Формат входного файла

В первой строке записано два числа n и m (1 ≤ n, m ≤ 200 000) — количество детей в ряду и количество событий, произошедших за все время. Во второй строке задано n натуральных чисел — рост каждого школьника в порядке следования в ряду. Рост детей не превосходит 2 ⋅ 10⁵. Далее в m строках задано описание событий: три числа q, l, r в каждой строке (0 ≤ q ≤ 1, 1 ≤ l ≤ r ≤ n). Число q показывает тип события: 0 показывает необходимость посчитать и вывести суммарный рост школьников на отрезке [l, r]; 1 показывает то, что дети на отрезке [l, r] "перевернули" свой отрезок. Все числа во входном файле целые.

Формат выходного файла

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

Примеры тестов

5 6
1 2 3 4 5
0 1 5
0 2 4
1 2 4
0 1 3
0 4 5
0 3 5

15
9
8
7
10

Задача C. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

Формат входного файла

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

Примеры тестов

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача D. Фаброзавры-дизайнеры ≡

Условие

Фаброзавры известны своим тонким художественным вкусом и увлечением ландшафтным дизайном. Они живут около очень живописной реки и то и дело перестраивают тропинку, идущую вдоль реки: либо насыпают дополнительной земли, либо срывают то, что есть. Для того, чтобы упростить эти работы, они поделили всю тропинку на горизонтальные участки, пронумерованные от 1 до N, и их переделки устроены всегда одинаково: они выбирают часть дороги от L-ого до R-ого участка (включительно) и изменяют (увеличивают или уменьшают) высоту на всех этих участках на одну и ту же величину (если до начала переделки высоты были разными, то и после переделки они останутся разными).

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

Формат входного файла

Первая строка входного файла содержит два числа N и M — длину дороги и количество запросов соответственно (1 ≤ N, M ≤ 10⁵). На второй строке содержатся N чисел, разделенных пробелами  — начальные высоты соответствующих частей дороги; высоты не превосходят 10⁴ по модулю. В следующих M строках содержатся запросы по одному на строке. Запрос + L~R~X означает, что высоту частей дороги от L-ой до R-ой (включительно) нужно изменить на X. При этом 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁴. Запрос ? L~R~X означает, что нужно проверить, есть ли между L-ым и R-ым участками (включая эти участки) участок, где дорога проходит точно на высоте X. Гарантируется, что 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁹.

Формат выходного файла

На каждый запрос второго типа нужно вывести в выходной файл на отдельной строке одно слово "YES", если нужный участок существует, и "NO" в противном случае.

Примеры тестов

10 5
0 1 1 3 3 3 2 0 0 1
? 3 5 2
+ 1 4 1
? 3 5 2
+ 7 10 2
? 9 10 3

NO
YES
YES

Задача E. Автоматизация склада ≡

Условие

Компания занимается автоматизацией склада. На складе хранятся n видов товаров, пронумерованных от 1 до n, каждый вид товара хранится в своём помещении. Товар вида i хранится в помещении с номером i.

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

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

В начале рабочего дня роботу поступил заказ на выдачу m товаров: a₁, a₂, …, a_m. Робот должен выдать товары именно в этом порядке. Для этого он последовательно выполняет следующие действия: открывает помещение, в котором лежит очередной товар, берет товар, закрывает помещение и выдаёт товар клиенту. После этого робот переходит к выдаче следующего товара.

Исходно электронные карты лежат в отсеке в следующем порядке, от верхней к нижней: b₁, b₂, …, b_n. Для каждого помещения в отсеке лежит ровно одна карта.

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

Требуется написать программу, которая по заданным целым числам n и m, последовательности выдаваемых товаров a₁, a₂, …, a_m и начальному положению карт в отсеке для хранения b₁, b₂, …, b_n определяет, какое минимальное количество действий придется совершить роботу, чтобы открыть все помещения в необходимом порядке. Для каждой вынутой карты необходимо также указать позицию, на которую её необходимо вернуть, чтобы добиться оптимального количества действий.

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

Первая строка входных данных содержит два целых числа n и m — количество видов товаров и количество товаров, которые необходимо выдать со склада.

Вторая строка содержит m целых чисел a₁, a₂, …, a_m — типы товаров, которые необходимо выдать со склада, перечисленные в том порядке, в котором это необходимо сделать.

Третья строка содержит n различных целых чисел b₁, b₂, …, b_n — порядок, в котором карты исходно находятся в отсеке для их хранения, перечисленные от верхней к нижней.

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

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

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

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

Ограничения

1 ≤ n, m ≤ 3 ⋅ 10⁵

1 ≤ a_i ≤ n

1 ≤ b_i ≤ n

Описание подзадач и системы оценивания

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

Пояснения к примерам

Во втором примере карты в отсеке робота перемещаются следующим образом:

Примеры тестов

1 1
1
1

1
1 

4 5
4 1 2 4 4
4 3 2 1

7
4 4 2 4 4 1 4 

2 2
1 2
2 1

3
2 2 2