مقدمه
قبل از این داده ساختار Segment Tree را به صورت تئوری مورد بحث قرار دادیم ، امروز مسئله UVA 12086 - Potentiometers یا مقاومت متغییر که با استفاده از این ساختمان داده قابل حل میباشد را پیاده سازی میکنیم.


متن مسئله
PDF مسئله از اینجا قابل دریافت است ، خلاصه متن این است که N مقاومت متغییر روی یک خط قرار گرفتند ، و مقدار اولیه هریک را داریم ، باید به تعداد M دستور پاسخ بدهیم دو نوع دستور داریم
نوع اول : مقدار مقاومت x را به r تغییر بده
نوع دوم : مقاومت معادل r تا l را چاپ کن ، که معادل با جمع تک تک مقاومت های این بازه میباشد.


راه حل
ابتدا راه حل ساده یعنی پیاده سازی همین کار با دو حلقه تو در تو به نظر درست می آید اما مرتبه این الگوریتم O(NM) میباشد که با توجه اینکه N میتواند تا 200000 باشد ، و M نیز میتواند تا 200000 باشد بطور تقریبی میتوان حدس زد که این الگوریتم نیاز به زمان اجرای 400 ثانیه ای تنها برای یک تست دارد و نتیجه این ارسال بدون شک Time Limit Executed میباشد ، برنامه میبایست زیر 3 ثانیه تمامی دستورات تمام تست ها را پاسخ گو باشد. 

ادامه مطلب