Interactive
Alex_KPR: — ...начиная где-то с декартовых деревьев, FFT и так далее, вбивание и отладка кода становятся напрягающими и довольно занудными задачами...
Kunyavsky: — А можно я придерусь к мелочи. Что делают в одном ряду по времени написания декартово дерево и FFT?
Alex_KPR: — это первое, что пришло в голову, где нужно много писать и есть где накосячить
Kunyavsky: — Я же сказал: придираюсь к мелочам. Просто на мой взгляд рядом поставлены вещи, одна из которых несравнимо легче по написанию
homo_sapiens: — Полностью согласен Фурье пишется вдвое может даже втрое быстрее чем дерево (но его обычно пихать надо руками и ногами)
Kunyavsky: — Я имел ввиду с точностью наоборот. Все таки очень специфичная тема.
homo_sapiens: — Видимо и правда на вкус и цвет...
Пришло время узнать, что же проще.
Вам предлагаются две последовательности из N целых чисел {x_i} и {y_i}.
Если вам больше нравится FFT, представьте, что это коэффициенты двух многочленов:
Найдите коэффициенты многочлена P(z)·Q(z).
Если же вам больше нравятся Декартовы деревья, представьте, что {x_i} — ключи, а {y_i} — приоритеты. Постройте Декартово дерево путем вставки в него последовательно всех N элементов (x_i, y_i). После каждой вставки выводите высоту получившегося дерева. Высота дерева — количество ребер на длиннейшем пути от какой-либо вершины к корню.
Для тех, кто выбрал FFT, напомним, что Декартово дерево — это двоичное дерево поиска по ключам, содержащимся в вершинах (x_i). И одновременно куча по приоритетам в вершинах (y_i). То есть, для каждой вершины дерева выполняется свойство, что все вершины из левого поддерева имеют ключи меньшие, чем в данной вершине, а все вершины из правого поддерева — большие. А также приоритет данной вершины больше приоритета ее сыновей.
Независимо от того, что же вы выбрали, автор убедительно просит не использовать в этой задаче prewritten code.
Входные данные
В первой строке число N. Во второй строке N различных целых чисел — {x_i}. В третьей строке N различных целых чисел — последовательность {y_i}.
Выходные данные
Если вы выбрали FFT, то выведите 2N-1 целых чисел — коэффициенты результирующего многочлена. Если Декартово дерево, то N целых чисел — высоты дерева после вставки в него каждой вершины.
Вообще, вы можете вывести и то, и то, но тогда оба результата будут проверяться на корректность.
Ограничения
1 ≤ N ≤ 50000
1 ≤ x_i ≤ 50000
1 ≤ y_i ≤ 50000
Гарантируется, что высота дерева не превысит 50.