e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - January 13 - Segment Tree

Пригоди Незнайки та його друзів

prb4496 Усі ми пам'яиаємо історію про те, як Незнайка зі своїми друзями літали на повітряній кулі подорожувати. Але не всі знають, що не усі чоловічки помістились у кулі, так як у неї була обмежена вантажопідйомність.

У цій задачі Вам необхідно взнати, скільки же чоловічків полетіло подорожувати. Відомо, що посадка у кулю не є оптимальною, а саме: чоловічки сідають у кулю у тій черзі, у якій вони стоять, як тільки комусь з них не вистачає місця, він і усі чоловічки, що залишились у черзі, повертаються і йдуть додому.

Вхідні дані

У першому рядку міститься кількість чоловічків n (1n106) у квітковому місті. У другому рядку вага кожного з чоловічків у тому порядку, у якому вони будуть сідати у кулю. Усі ваги натуральні числа і не перевищують 109. Далі йде кількість запитів m (1m105). Кожен запит являє собою один рядок. Якщо перше число у рядку дорівнює одиниці, то далі йде ще одне число v (1v109) – вантажопідйомність повітряної кулі. Якщо ж воно рівне двом, то далі йде два числа x (1xn) та y (1y109) - це означає, що вага чоловічка, який стоїть на позиції x, тепер дорівнює y.

Вихідні дані

Для кожного запиту під номером один виведіть в окремому рядку кількість чоловічків, які помістились у кулю.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
Вихідні дані #1
3
2
2
0
Автор Олександр Бурков
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року