مسئله‌ی زیر ۳ قسمت دارد، شما برای حل هر قسمت می‌توانید قسمت‌های قبلی آن را درست فرض کرده از حکم آن‌ها برای حل آن استفاده کنید، مثلا می‌توانید برای حل قسمت (ب) بدون حل کردن قسمت (الف) از حکم آن برای حل (ب) کمک بگیرید.

خبر رسیده که قراره یه خانم خارجی بیاد باشگاه و یه بازدید کاملا رسمی از المپیادهای مختلف از جمله المپیاد همیشه در صحنه کامپیوتر داشته باشه. چون بروبچه‌های ماهمیشه رتبه‌های خوبی رو در عرصه‌های بین‌المللی داشته‌اند، کمیته‌ی بازدید قصد دارن که بعضی از دوستان رو محک بزنن.

شور و هیجان دوره تابستانی را فرا گرفته بود. ولی دوستان نفوذی موفق شدند که شرح این آزمون رو پیدا کنن. یعنی فهمیدن که چه‌جوری قراره دوستان ما امتحان بشن.

قضیه از این قراره که یه لیست $n$-تایی از اعداد به صورت $a_1$ تا $a_n$ وجود داره که دست تیم بازدیدکننده است. سوالاتی که به بچه‌ها داده می‌شه به شکل زیر است:

• کوچک‌ترین عدد در بین $a_i,a_{i+1},...,a_j$ کدام است؟

نکته این‌جاست که دوستان هیچ مکثی نباید در پاسخ دادن به این سوال داشته باشن. به عبارت بهتر باید در زمان $O(1)$ به سوال جواب بدن.

الف) وای چه بد شد!! ولی نه. قرار شده به محض ورود بازدیدکنندگان به باشگاه، فهرست اعداد رو ازشون می‌گیرن و به بچه‌ها می‌رسونن تا خودشون رو برای جواب دادن آماده کنن. اون طوری توی برنامه‌ی بازدید مشخصه کامپیوتر آخرین محل بازدیده و بچه‌ها از مرتبه‌ی زمانی $O(n.logn)$ وقت دارن که هر کاری دوست دارن بکنن. شما باید برای دوستان الگوریتم‌هایی از مرتبه‌ی زمانی $O(n.logn)$ و $O(1)$ برای زمان آماده‌سازی و زمان پاسخ‌گویی ارائه کنید.

ب) یه خبر بد! تیم بازدیدکننده یه خرده شک کرده و لذا زودتر از کامپیوتر بازدید خواهد کرد. حالا برای آماده‌سازی تنها از مرتبه‌ی $O(n)$ زمان خواهیم داشت. اما معلوم شده که در فهرست اعداد اختلاف دو عدد متوالی دقیقا برابر ۱ می‌باشد. این بار نیز چاره‌ای برای خود بیاندیشید.

ج) بله دیگه! مثل این‌که یه سوال دیگه هم وجود داره! یه درخت ریشه‌دار به ما میدن و سوال‌ها از این قرار است:

پایین‌ترین جد مشترک رئوس $a$ و $b$ چیست؟

این بار نیز سوالات را بایستی در زمان $O(1)$ پاسخ داد ولی پس از به دست آوردن درخت مسئله به اندازه‌ی $O(n)$ فرصت داریم.

• سوال بعد
• سوال قبل