یک دنباله‌ی ‎$A$‎ از اعداد مثبت متفاوت به طول ‎$n$‎ به شما داده شده است. یک ماشین کمکی داریم که در یک حرکت بزرگ‌ترین زیردنباله‌ی یکنوای (زیردنباله‌‎ی صعودی یا نزولی) را در ‎$A$‎ پیدا کرده و با حذف این زیردنباله آن‌را در دنباله‌ی ‎$B$‎ ذخیره می‌کند. در ضمن دو متغیر ‎$n$‎ و ‎$m$‎ هم داریم که نشان‌دهنده‌ی طول ‎$A$‎ و ‎$B$‎ هستند. این ماشین پس از عملیاتش مقدار این دو متغیر را نیز درست نگه می‌دارد. مثلاً اگر آرایه‌ی ما در ابتدا ‎$A=(4‎, ‎5‎, ‎3‎, ‎10‎, ‎20‎, ‎7‎, ‎9‎, ‎6‎, ‎5.5‎, ‎4.5‎, ‎2)$‎ باشد، خروجی ماشین به صورت ‎$A=(4‎, ‎5‎, ‎3‎, ‎20‎, ‎7)$‎، ‎$n=5$‎، ‎$B=(10‎, ‎9‎, ‎6‎, ‎5.5‎, ‎4.5‎, ‎2)$‎ و ‎$m=6$‎ است. تکرار این عمل ما را به دنباله‌های ‎$A=(3,7)$‎ و ‎$B=(4,5,20)$‎ با ‎$n=2$‎ و ‎$m=3$‎ می‌رساند.

اگر طول زیردنباله‌ی حذف‌شده ‎$k$‎ باشد زمان اجرای این عمل ‎$O(k)$‎ خواهد بود. به شما در ابتدا ‎$O(n)$‎ زمان داده شده است تا خود را برای مرحله‌ی بعدی که جستجو است آماده کنید. در مرحله‌ی دوم در هر سوال به شما عدد ‎$x$‎ داده می‌شود و شما باید بفهمید که آیا ‎$x$‎ جزٔ ‎$n$‎ عدد اولیه در آرایه‌ی ‎$A$‎ بوده‌است یا خیر. زمان اجرای شما به ازای هر ورودی باید ‎$O(\sqrt{n}\log(n))$‎ باشد.

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