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



Результат



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


From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

gltronred: (Default)
gltronred

June 2016

S M T W T F S
   1234
567891011
12131415161718
192021 22232425
2627282930  

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 26th, 2017 02:29 am
Powered by Dreamwidth Studios