Алгоритмическая задача про грузы и весы

[KappaGolden]

Джек нашел $N$ камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер $1$, следующий – $2$ и так далее, самый тяжелый получил номер $N$.

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

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

Входные данные
Первая строка содержит целое число $N$ $(1\leqslant N\leqslant 100000)$.

Каждая из следующих N строк содержит по два целых числа: $R$ $(1\leqslant R\leqslant N)$ и $S$ $(1\leqslant S\leqslant 2)$. $R$ – номер камня, который будет положен на чашу $S$. Все $R$ будут различны.

Выходные данные
Выведите $N$ строк – по одной для каждого камня. Если после добавления соответствующего камня чаша $1$ тяжелее, выведите $«<»$. Если сторона $2$ тяжелее, выведите $>$. Если невозможно определить, в каком состоянии будут весы, выведите $«?»$.

Помогите! Я не знаю как решать эту задачу. Подскажите идею, как её можно решить. Я понимаю, что её нужно решать с помощью дерева отрезков, но в голову приходит лишь тупой перебор, в стиле смотреть, если в одной куче есть, скажем, одна машинка с номером 5, а в другой, с номерами: 1,2,3,4 - то сказать, что тяжелее мы не сможем, иначе если найдется больше, или столько же грузов с номерами большими, чем в другой, то говорить, что в та куча будет тяжелее.

[Pphantom]

Тема перемещена из форума «Computer Science» в форум «Карантин»
по следующим причинам:

- неинформативный заголовок;
- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Computer Science»

-- 12.04.2020, 17:27 --

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

[KappaGolden]

Как я понимаю, мы смотрим на номера из первой чаши, и если мы можем составить пары $(a , b)$ где $a > b$ и $a$ из второй чаши. Другими словами, я говорю, что мы можем сказать, что куча 1 больше кучи 2, тогда когда каждому элементу, кучи 1 соответствует меньший элемент кучи 2(а если нет пары, то будем считать что его вес -1)

[Pphantom]

Да, если для каждого груза из "меньшей" кучи можно найти свой больший груз из большей.

Ну и что, ни на какие мысли по части реализации это не наводит?

[KappaGolden]

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

Но мне кажется, что моё решение слишком уж медленное.

[Pphantom]

Да, примерно так, но только предыдущее состояние можно хранить и учитывать.

А что, в условии оговаривалось время?

[KappaGolden]

Ну, ограничение 1 секунда. Я не знаю насколько хорошей должна быть асимптотика, чтобы при таких $N$ уложиться в это время. Но эта задача из темы, которая называется: "Дерево Фенвика, дерево отрезков". Так что мой алгоритм мне не внушает доверия.

[Pphantom]

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

[KappaGolden]

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

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

[Pphantom]

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

[KappaGolden]

Хорошо, дерево Фенвика - это такая структура данных, которое обладает некоторыми свойствами, такими как, изменение элемента и вычисление суммы на сегменте за быстро(за логарифм).

[Pphantom]

Уж очень обтекаемо... а дерево Фенвика для максимума? Посмотрите, неужели не видно?

[KappaGolden]

Хммм... Насколько я понял, мы считываем всю последовательность добавлений на чаши в два дерева Фенвика - в первую чашу - первое дерево Фенвика, вторая чаша - второе дерево Фенвика. Затем мы будем выполнять запросы максимума на нужном сегменте.

Но мне кажется, что я неверно понял ваш посыл...

[Pphantom]

Ну да, это и есть решение.