gltronred: (Default)
[personal profile] gltronred
Всё забыл


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 карандашей). Гарантируется, что система работает совершенно исправно.



Результат



Результаты запросов на суммирование, каждый в отдельной строке


Profile

gltronred: (Default)
gltronred

August 2017

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 21st, 2017 06:56 am
Powered by Dreamwidth Studios