Задача №114322. Субмарины
\(N\) субмарин бороздят просторы океана. Они расположены в ряд с первой по \(N\)-ю, расстояние между соседними по горизонтали \(5 км\). Они плывут в одну сторону в этом же порядке (впереди - первая) с одинаковыми постоянными скоростями, каждая на своей глубине. Каждая может послать сигнал, который получит ближайшая (по евклидову расстоянию на плоскости) из плывущих сзади, которая расположена глубже лодки, посылающей сигнал, если такая есть, и никто больше.
Происходят 2 вида событий:
"Поменять две соседних субмарины местами" - в нем указывается число \(i\) - номер одной из них, другая имеет номер \(i+1\). Действие происходит мгновенно, субмарины остаются на своих же глубинах.
"Отправить сигнал" – каждая субмарина отправляет сигнал.
Напишите программу, которая для каждого события второго типа посчитает, сколько максимум сигналов получила одна субмарина.
В первой строчке даны натуральные \(N\) и \(M\), разделённые пробелом.
Во второй строчке через пробел даны \(N\) натуральных ненулевых чисел, не превышающих \(3 000 000\) - глубины субмарин в миллиметрах порядке следования подводных лодок \(x\).
На каждой из следующих \(M\) строк дано по одному целому неотрицательному чиислу. Если это \(0\), то это действие первого типа, все издают сигнал; если это \(i>0\), то это значит, что субмарины \(i\) и \(i+1\) должны поменяться местами.
Для каждого события отправки сигналов субмаринами выведите в отдельной строке ответ – максимальное количество сигналов, которые получит одна из субмарин за это действие.
1. (20 баллов) \(1 < N\leq 1000\), \(1\leq M\leq 100\).
2. (30 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 20\).
3. (50 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 100000\).
Мы считаем субмарины точками.
Заметим, что субмарина, которая должна получить сигнал по описанию, при заданных горизонтальных расстояниях между лодками и возможными глубинами всегда не более, чем одна.
9 3 100 300 50 1000 1100 1200 500 400 600 0 1 0
2 3