e-olymp 3358. Чёрный ящик

by

2

Задача

В черный ящик кладутся листки с написанными на них числами. На каждом листке — ровно одно целое число. Иногда некоторые листки исчезают из ящика. После каждого события (когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести число, которое встречается чаще всего на листках, находящихся в данный момент в ящике. Если таких чисел несколько, выведите наименьшее.

Входные данные

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

  • [latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
  • [latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

Выходные данные

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные Выходные данные
3
+ 1
— 1
+ 2		 1
0
2
6
+ 1
+ 1000000
— 1
+ 4
+ 4
— 1000000		 1
1
1000000
4
4
4
8
+ 71
+ 91
+ 99
+ 71
— 71
— 91
— 71
— 99		 71
71
71
71
71
71
99
0

Код программы

Решение задачи

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

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Related Images:

2 thoughts on “e-olymp 3358. Чёрный ящик”

    • Добрый день, Игорь Евгеньевич!
      Я посмотрел решение Вадима и могу рассказать, в чем его неэффективность.
      1. Слишком универсальный (обобщённый) код. Реализовано универсальное дерево отрезков. Используется класс с методами, что теоретически может создавать оверхед(хотя и не должно, т.к. класс только один, наследования нет, а значит, оверхеду от позднего связывания неоткуда взяться). В любом случае, на ACM писать классы если можно обойтись функциями как-то не принято.
      2. Медленный ввод. В решении Вадима используются scanf и printf, но ввиду тривиальности ввода в этой задаче, его можно ускорить с помощью посимвольного ввода (что и делается в моем решении).
      4. Решение задачи в в общем случае без учета особенностей конкретной задачи. Нет смысла считать то, что уже посчитано. У Вадима в коде, вычисляющем ответ на запрос, есть такая строка:
      printf(«%u\n», (box.result_on_segment(0, 1000000)).number);
      Но ведь, поскольку нас интересует ответ на запрос на отрезке, покрывающем всё дерево, мы можем просто напрямую обратиться к нулевому (или первому, в зависимости от реализации) элементу дерева. К тому же, из-за того, что размер дерева не является степенью двойки, то это ещё и работает за O(log n). А ведь на запросы чтения можно отвечать за O(1).
      3. Использование неправильной структуры данных для решения задачи. В ACM всегда надо смотреть на ограничения. В данной задаче числа могут быть до 10^6, из-за чего при использовании обычного дерева отрезков нам приходится работать с деревом отрезков на 10^6 элементов. В частности, уходит время на процедуру построения дерева. А ведь запросов всего 10^5. То есть мы строим дерево размером 10^6 из нейтральных элементов независимо от размера ввода. И используем в конечном счете не более 1/10 элементов из этого дерева. Вместо этого предлагается использовать неявное дерево отрезков. В таком случае будут создаваться только те элементы дерева, которые реально используются (плюс будет ускорение на тестах маленького размера). А процедура построения дерева вообще не требуется.

      Прикинем асимптотику обоих решений (не исключительно в терминах big-O-notation, а учитывая все компоненты):
      n — количество элементов дерева (1000000)
      q — количество запросов
      Решение Вадима:
      Построение дерева — O(n)
      Обновление дерева — O(log n) на запрос
      Получение ответа — O(log n) на запрос
      Итого время работы: C1*O(n)+C2*O(q*log n)+C3*O(q*log n),
      где C1, C2, C3 — константы

      Моё решение:
      Обновление дерева — O(log n) на запрос
      Получение ответа — O(1) на запрос
      Итого время работы: C1*O(q*log n)+C2*O(1),
      где C1, C2 — константы

Добавить комментарий