e-olymp 4496. Приключение Незнайки и его друзей

Задача

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

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

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

В первой строке содержится количество человечков $n$ $(1 \leqslant n \leqslant 10^{6})$ в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают $10^{9}.$ Далее следует количество запросов $m$ $(1 \leqslant m \leqslant 10^{5})$. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число $v$ $(1 \leqslant v \leqslant 10^{9})$ – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа $x$ $(1 \leqslant x \leqslant n)$  и  $y$ $(1 \leqslant y \leqslant 10^{9})$ — это значит, что вес человечка, стоящего на позиции $x$, теперь равен $y$.

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

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

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 3
2 1 8
1 3
2
0
3 5
1 3 4 5 6
5
1 7
1 9
2 3 5
1 7
2 3 1
2
3
2
4 1
5
3
1 3
2 1 2
1 3
0
1
5 1
1
2
1 4
1 3
1
1

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

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

Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.

Ссылки