Задача
Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.
В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.
Входные данные
В первой строке содержится количество человечков $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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> using namespace std; struct tree { long * tr; tree(int n) { tr = new long[4 * n + 1]; } void build(int * arr, int v, int l, int r) { if (l == r) tr[v] = arr[l]; else { int mid = (l + r) / 2; build(arr, v * 2, l, mid); build(arr, v * 2 + 1, mid + 1, r); tr[v] = tr[v * 2] + tr[v * 2 + 1]; } } void update(int v, int l, int r, int pos, int val) { if (l == r) tr[v] = val; else { int mid = (l + r) / 2; if (pos <= mid) update(v * 2, l, mid, pos, val); else update(v * 2 + 1, mid + 1, r, pos, val); tr[v] = tr[v * 2] + tr[v * 2 + 1]; } } int find(int v, int l, int r, int max) { if (l == r) return (tr[v] <= max); int mid = (l + r) / 2; if (tr[v * 2] > max) return find(v * 2, l, mid, max); else return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]); } }; int main() { int n, m, * arr; cin >> n; arr = new int[n + 1]; for (int i = 1; i <= n; ++i) cin >> arr[i]; tree tr(n); tr.build(arr, 1, 1, n); cin >> m; int com, x, y, v; for (int i = 0; i < m; ++i) { cin >> com; switch (com) { case 1: { cin >> v; cout << tr.find(1, 1, n, v) << '\n'; break; } case 2: { cin >> x >> y; tr.update(1, 1, n, x, y); break; } } } return 0; } |
Решение задачи
Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.
Как по мне, то Дерево отрезков тут излишнее, мы с вами разобрали такую интересную структуру данных как дерево Фенвика, ибо для запросов на префиксе и изменение в точке нет ничего удобней вышеупомянутой структуры, ну и да ответ на запрос будет искаться бинпоиском, если я не ошибаюсь асимптотика такая же $O(logn)$ это запрос на изменение и сумму. Ну а для запроса количества людей это $log^2n$. Не стреляйте из пушки по воробьям, эти функции Фенвиком займут не больше 10-15 строк и меньше возможностей словить баг.
… или хотя бы отступы поставьте
Спасибо, исправила.