Старые олимпиады: 2007 - интернет - D
Всё забыл
D. Шведские карандаши
Ограничение времени: 2 сек
Ограничение памяти: 64 мб
Предыстория
Пушистый Волк ворочается в своей мягкой постели. Ему снова видится все тот же самый кошмар: как они с товарищем идут на охоту в одной из бинарных чащ; как сзади начинают трещать сучья и загораться ветки; как издали доносится утробный медвежий рык; как огромное дерево обрушивает прямо на голову его лучшего друга; как потом он прибежал к самому мудрому волку в чаще и как этот волк издал Клич; как началась Великая Война.
В последнее время Пушистому Волку часто видится этот сон во всех подробностях. И одна странная деталь занимает все внимание Пушистого Волка - подрубленное дерево, всё в следах от чьих-то острых зубов. И ведь зубы-то... не медвежьи!
Условие
Теперь же Пушистому Волку необходимо как следует отоспаться. Завтра ему предстоит огромный труд по сооружению системы слежения за карандашами для гипермаркета IKEA, недавно открытого в Двоичном Лесу (притом в Бобровом Квартале). Как известно, в гипермаркетах IKEA можно приобрести весь спектр разнообразнейших фанфрелюшечек, в том числе и бесплатные карандаши. На самом деле каждый из этих карандашей содержит миниатюрный радиопередатчик, который позволяет отслеживать все передвижения этого карандашика. Но бобры ничего не знают о радиопередатчиках, а потому уносят их из гипермаркета сотнями и тысячами (и даже иногда воруют их друг у друга). Иногда, правда, им надоедает играть с карандашами, и они выкидывают их на свалку.
Все дома в Бобровом квартале перенумерованы числами от 1 до N. Система слежения позволяет отследить перемещение любого количества карандашей (из гипермаркета или между двумя домами, или между домом и свалкой). Но система не может эффективно ответить на вопрос, сколько всего карандашей находятся в домах с номерами от i до j; она начинает зависать и рисовать на экране забавные бантики, что в принципе, неудивительно; ведь проектировал ее не кто иной, как знаменитый программист Даня Зайкин! А ответ на этот вопрос очень важен, ибо ради этого вся система и затевалась - для выявления наиболее клептоманских подрегионов бобрового квартала.
Пушистый Волк слышал, что эту задачу решил некто Питер М. Фенвик. Но статью его он никак сыскать не смог, хотя и пользовался И-Так-Понятно-Какой-Поисковой-Системой. Возможно, вам повезет больше?
Исходные данные
В первой строке два натуральных числа, N(1<=N<50000) и L(1<=L<=100000) - количество запросов к системе. Далее в L строчках идут запросы следующего вида:
0 A K - в дом с номером А принесли К карандашей;
1 A K - из дома с номером А выкинули К карандашей;
2 A B K - из дома с номером А в дом с номером В перенесли К карандашей;
3 A B - подан запрос на вычисление суммарного количества карандашей в домах, нумерованных от A до В (включая концы)
Первоначально предполагается, что в домах нет ни единого икеевского карандаша ( и в каждом доме может присутствовать не более 25000 карандашей). Гарантируется, что система работает совершенно исправно.
Результат
Результаты запросов на суммирование, каждый в отдельной строке
D. Шведские карандаши
Ограничение времени: 2 сек
Ограничение памяти: 64 мб
Предыстория
Пушистый Волк ворочается в своей мягкой постели. Ему снова видится все тот же самый кошмар: как они с товарищем идут на охоту в одной из бинарных чащ; как сзади начинают трещать сучья и загораться ветки; как издали доносится утробный медвежий рык; как огромное дерево обрушивает прямо на голову его лучшего друга; как потом он прибежал к самому мудрому волку в чаще и как этот волк издал Клич; как началась Великая Война.
В последнее время Пушистому Волку часто видится этот сон во всех подробностях. И одна странная деталь занимает все внимание Пушистого Волка - подрубленное дерево, всё в следах от чьих-то острых зубов. И ведь зубы-то... не медвежьи!
Условие
Теперь же Пушистому Волку необходимо как следует отоспаться. Завтра ему предстоит огромный труд по сооружению системы слежения за карандашами для гипермаркета IKEA, недавно открытого в Двоичном Лесу (притом в Бобровом Квартале). Как известно, в гипермаркетах IKEA можно приобрести весь спектр разнообразнейших фанфрелюшечек, в том числе и бесплатные карандаши. На самом деле каждый из этих карандашей содержит миниатюрный радиопередатчик, который позволяет отслеживать все передвижения этого карандашика. Но бобры ничего не знают о радиопередатчиках, а потому уносят их из гипермаркета сотнями и тысячами (и даже иногда воруют их друг у друга). Иногда, правда, им надоедает играть с карандашами, и они выкидывают их на свалку.
Все дома в Бобровом квартале перенумерованы числами от 1 до N. Система слежения позволяет отследить перемещение любого количества карандашей (из гипермаркета или между двумя домами, или между домом и свалкой). Но система не может эффективно ответить на вопрос, сколько всего карандашей находятся в домах с номерами от i до j; она начинает зависать и рисовать на экране забавные бантики, что в принципе, неудивительно; ведь проектировал ее не кто иной, как знаменитый программист Даня Зайкин! А ответ на этот вопрос очень важен, ибо ради этого вся система и затевалась - для выявления наиболее клептоманских подрегионов бобрового квартала.
Пушистый Волк слышал, что эту задачу решил некто Питер М. Фенвик. Но статью его он никак сыскать не смог, хотя и пользовался И-Так-Понятно-Какой-Поисковой-Системой. Возможно, вам повезет больше?
Исходные данные
В первой строке два натуральных числа, N(1<=N<50000) и L(1<=L<=100000) - количество запросов к системе. Далее в L строчках идут запросы следующего вида:
0 A K - в дом с номером А принесли К карандашей;
1 A K - из дома с номером А выкинули К карандашей;
2 A B K - из дома с номером А в дом с номером В перенесли К карандашей;
3 A B - подан запрос на вычисление суммарного количества карандашей в домах, нумерованных от A до В (включая концы)
Первоначально предполагается, что в домах нет ни единого икеевского карандаша ( и в каждом доме может присутствовать не более 25000 карандашей). Гарантируется, что система работает совершенно исправно.
Результат
Результаты запросов на суммирование, каждый в отдельной строке