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

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

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

Вход.  В первой строке содержится количество человечков n (1 ≤ n ≤ 10⁶) в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают 10⁹. Далее следует количество запросов m (1 ≤ m ≤ 10⁵). Каждый запрос представляет собой одну строку. Первое число t в строке – тип запроса.

· Если t = 1, то далее следует еще одно число v (1 ≤ v ≤ 10⁹) – грузоподъемность воздушного шара.

· Если t = 2, то далее следует два числа x (1 ≤ x ≤ n) и y (1 ≤ y ≤ 10⁹) – вес человечка на позиции x становится равным y.

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

Пример входа	Пример выхода
5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3	3 2 2 0

РЕШЕНИЕ

структуры данных - дерево отрезков, единичная модификация

Анализ алгоритма

Для решения задачи следует реализовать дерево отрезков, поддерживающее сумму элементов, модификацию единичного элемента (первое число запроса равно двум) и вычисление специфической функции (количество человечков, которое поместится в воздушный шар).

Если первое число в запросе равно единице, то необходимо найти количество последовательных элементов (начиная с первого), сумма которых не превышает грузоподъемность воздушного шара v.

Реализация алгоритма

Объявим массив SegTree для хранения дерева отрезков. Входную последовательность чисел храним в массиве m. Дерево отрезков поддерживает операцию суммы. Веса человечков не больше 10⁹, всего человечков не более 10⁶, следовательно суммы на отрезках (значения в ячейках SegTree) не будут выходить за границу 64 битового целочисленного типа.

vector<long long> SegTree;

vector<int> m;

Функция Buildtree по массиву m строит дерево отрезков, поддерживающее сумму.

void BuildTree(int v, int lpos, int rpos)

{

if (lpos == rpos) SegTree[v] = m[lpos];

else

{

int mid = (lpos + rpos) / 2;

BuildTree(2 * v, lpos, mid);

BuildTree(2 * v + 1, mid + 1, rpos);

SegTree[v] = SegTree[2 * v] + SegTree[2 * v + 1];

}

}

Функция Get возвращает количество последовательных элементов (начиная с первого), сумма которых не превышает грузоподъемность воздушного шара w.

int Get(int v, int lpos, int rpos, long long w)

{

Если отрезок [lpos; rpos] состоит из одного элемента, то ответ равен 1, если человечка с весом SegTree[v] можно поместить в шар, и 0 иначе.

if (lpos == rpos) return SegTree[v] <= w;

Находим середину отрезка mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Если сумма весов SegTree[2*v] человечков в левом поддереве дерева отрезков больше w, то все человечки из левого поддерева не войдут в воздушный шар. Поэтому ответ следует искать только в левом поддереве.

if (SegTree[2 * v] > w)

return Get(2 * v, lpos, mid, w);

else

Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно mid – lpos + 1 с общим весом SegTree[2*v]), а также человечков из правого поддерева начиная с позиции mid + 1 и далее пока общая сумма весов человечков из правого поддерева не станет больше w – SegTree[2*v].

return mid - lpos + 1 +

Get(2 * v + 1, mid + 1, rpos, w - SegTree[2 * v]);

}

Функция Update в позицию pos записывает значение val. Вершине v соответствует отрезок [lpos, rpos].

void Update(int v, int lpos, int rpos, int pos, int val)

{

if (lpos == rpos) SegTree[v] = val;

else

{

int mid = (lpos + rpos) / 2;

if (pos <= mid) Update(v * 2, lpos, mid, pos, val);

else Update(v * 2 + 1, mid + 1, rpos, pos, val);

SegTree[v] = SegTree[2 * v] + SegTree[2 * v + 1];

}

}

Основная часть программы. Читаем входную последовательность чисел в массив m, начиная с первого индекса.

scanf("%d", &n);

SegTree.resize(4 * n + 10);

m.resize(n + 1);

for (i = 1; i <= n; i++) scanf("%d", &m[i]);

Строим дерево отрезков по элементам массива m[1..n].

BuildTree(1,1,n);

Последовательно обрабатываем запросы.

scanf("%d",&q);

for(i = 0; i < q; i++)

{

scanf("%d",&op);

if (op == 1)

{

scanf("%d",&Weight);

printf("%d\n",Get(1,1,n,Weight));

} else

{

scanf("%d %d",&x,&y);

Update(1,1,n,x,y);

}

}