مساله «آرایه قوی»

دنباله a_۱, a_۲, ..., a_n به شما داده شده است. زیردنباله a_L, ..., a_R را از این دنباله در نظر بگیرید. K_s برابر با تعداد بارهایی است که عدد s در این زیر دنباله ظاهر شده است. قدرت عدد s برابر است با K_s.K_s.s. قدرت زیردنباله برابر با مجموع قدرت تمام اعداد طبیعی است (چون تعداد اعداد دنباله محدود است قدرت زیر دنباله نیز محدود است). دنباله a_۱, a_۲, ..., a_n به شما داده می‌شود. شما باید در تعدادی پرسش مقدار L و R را دریافت کنید و قدرت زیردنباله a_L, ..., a_R را چاپ کنید. می‌دانیم تعداد پرسش‌ها و تعداد اعداد دنباله از ۲۰۰،۰۰۰ بیشتر نیست. همچنین هر عضو دنباله بین ۱ تا ۱۰۰۰،۰۰۰ است.

راه حل

اگر قدرت بازه [i, j] را داشته باشیم و در حافظه‌ای مقادیر K_s را نیز ذخیره کرده باشیم بدیهیست که می‌توانیم در O(۱) قدرت یکی از بازه های [i, j+۱]، [i, j-۱]، [i-۱, j] یا [i+۱, j] را حساب کنیم. به عبارتی می‌توانیم یکی از سرهای بازه را یک واحد جابه‌جا کنیم و قدرت جدید و مقادیر K_s را نیز داشته باشیم. حال اگر بخواهیم از بازه [i, j] به بازه [p, q] برسیم می‌توانیم با |i-p|+|j-q| حرکت این کار را انجام دهیم. ایده حل این مساله این است که بازه‌های پرسش را طوری مرتب کنیم که وقتی از اولین بازه شروع کنیم و بازه‌ها را به ترتیب پردازش کنیم تعداد حرکت ها مجموعا از O(n*sqrt(n)) باشد. این روش مرتب کردن بازه ها را در ادامه توضیح می‌دهیم. برای راحتی محاسبات فرض می‌کنیم تعداد پرسش‌ها و طول دنباله باهم برابر و n است.

دنباله را به sqrt(n) ناحیه به طول  sqrt(n)تقسیم کنید. حال بازه‌های پرسش را به ترتیب ناحیه ای که از آن شروع می‌شوند مرتب کنید. اگر ناحیه شروع دو بازه برابر بود آن دو را طبق نقطه پایان‌شان مرتب کنید. ادعا می‌کنیم پردازش بازه‌ها به این ترتیب در مجموع O(n*sqrt(n)) حرکت نیاز دارد. زیرا ابتدای بازه در هر مرحله یا در همان ناحیه جابجا می‌شود با به ناحیه مجاور بعدی می‌رود. هر کدام از این دو نوع حرکت هزینه اش O(sqrt(n)) است. پس چون n بازه داریم مجموع حرکت ابتدای بازه از O(n*sqrt(n)) است. همچنین به ازای هر ناحیه بازه هایی که شروع‌شان در آن ناحیه است بر حسب پایان شان مرتب شده. پس انتهای بازه در هر ناحیه مجموعا O(n) حرکت می‌کند. چون sqrt(n) ناحیه داریم مجموع حرکت های انتهای بازه O(n*sqrt(n)) است. در نتیجه پیچیدگی زمانی الگوریتم O(n*sqrt(n)) است.

لینک سوال اصلی