Задача №114690. Фокус с подмножествами
Ваня придумал интересный фокус с множеством целых чисел.
Пусть у фокусника есть множество положительных целых чисел \(S\). Он называет некоторое положительное целое число \(x\). Зритель должен выбрать, не показывая фокуснику, некоторое подмножество \(S\) (возможно пустое). После этого зритель называет фокуснику размер выбранного подмножества. Фокус заключается в том, что после этого фокусник отгадывает: верно ли, что сумма элементов выбранного подмножества не превосходит \(x\). Для пустого подмножества сумма предполагается равной \(0\).
Ване очень понравился этот фокус, поэтому он начал готовиться к тому, чтобы показать его публике. Для этого он приготовил некоторое множество различных положительных целых чисел \(S\). Конечно, Ваня хочет, чтобы фокус обязательно получился. Он называет положительное целое число \(x\) неудачным , если не может быть точно уверен, что фокус пройдет удачно для любого подмножества, которое выберет зритель.
Чтобы оценить, насколько хорошее множество \(S\) он выбрал, он хочет посчитать количество неудачных положительных целых чисел для него.
Также Ваня планирует протестировать различные множества \(S\). Поэтому он просит вас написать программу, которая найдет количество неудачных положительных целых чисел для изначального множества \(S\) и для множества \(S\) после каждого изменения. Ваня сделает \(q\) изменений своего множества, каждое изменение будет одного из двух видов:
- Добавить новое число \(a\) в множество \(S\).
- Удалить некоторое число \(a\) из множества \(S\).
В первой строке находятся два целых числа \(n\), \(q\) (\(1 \leq n, q \leq 200\,000\)) — размер изначального множества \(S\) и количество изменений.
В следующей строке находятся \(n\) различных целых чисел \(s_1, s_2, \ldots, s_n\) (\(1 \leq s_i \leq 10^{13}\)) — элементы изначального множества \(S\).
В каждой из следующих \(q\) строк находятся два целых числа \(t_i\), \(a_i\) (\(1 \leq t_i \leq 2\), \(1 \leq a_i \leq 10^{13}\)), описывающих очередное изменение.
- Если \(t_i = 1\), то это операция добавления нового числа \(a_i\) в множество \(S\). Гарантируется, что этого числа не было в множестве \(S\) до выполнения операции.
- Если \(t_i = 2\), то это операция удаления числа \(a_i\) из множества \(S\). Гарантируется, что это число было в множестве \(S\) до выполнения операции.
Выведите \(q + 1\) строку.
В первой строке выведите количество неудачных положительных целых чисел для изначального множества \(S\). В следующих \(q\) строках выведите количество неудачных положительных чисел для множества \(S\) после каждого изменения.
В первом тесте изначальное \(S = \{1, 2, 3\}\). Для этого множества фокус может не получиться при \(x \in \{1, 2, 3, 4\}\). Например, если \(x = 4\), то зритель может загадать подмножество \(\{1, 2\}\), сумма элементов которого равна \(3 \leq x\), а может загадать подмножество \(\{2, 3\}\), сумма элементов которого равна \(5 > x\). Однако в обоих случаях зритель назовет фокуснику размер подмножества \(2\), поэтому он не сможет точно сделать правильный ответ. При этом поскольку подмножество размера \(3\) единственно, а сумма в любом подмножестве меньшего размера не превосходит \(5\), все \(x \ge 5\) не являются неудачными.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Ограничения | ||||||
| Группа | Баллы | \(n\) | \(q\) | Доп. ограничения | Необх. группы | Комментарий |
| 0 | 0 | — | — | — | — | Тесты из условия. |
| 1 | 10 | \(n \leq 12\) | \(q \leq 100\) | все \(|S| \leq 12\) | 0 | |
| 2 | 10 | \(n \leq 100\) | \(q \leq 100\) | \(s_i, a \leq 100\) | 0 | |
| 3 | 20 | \(n \leq 2000\) | \(q \leq 2000\) | — | \(0\) – \(2\) | |
| 4 | 15 | \(n \leq 50\,000\) | \(q \leq 50\,000\) | — | \(0\) – \(3\) | |
| 5 | 15 | \(n \leq 100\,000\) | \(q \leq 100\,000\) | — | \(0\) – \(4\) | |
| 6 | 15 | \(n \leq 150\,000\) | \(q \leq 150\,000\) | — | \(0\) – \(5\) | Offline-проверка. |
| 7 | 15 | — | — | — | \(0\) – \(6\) | Offline-проверка. |
3 11 1 2 3 2 1 1 5 1 6 1 7 2 6 2 2 2 3 1 10 2 5 2 7 2 10
4 1 6 12 19 13 8 2 10 3 0 0