- محدودیت زمان: ۸ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
- منبع: آزمون نهایی اول دوره ۲۷ المپیاد کامپیوتر
زمان زیادی تا کانتست نمانده بود و آنیتا دیگر حوصله نداشت برای سوالات داستان بسازد، برای همین او از شما میخواهد که سوال زیر را حل کنید.
یک دنباله به طول \(n\) از اعداد \(1\) تا \(n\) داده شده است و هر بار یکی از دو نوع درخواست زیر داده میشود:
نوع اول: یک بازه از دنباله و دو عدد \(x\) و \(y\) داده میشود و تمام عنصرهای \(x\) آن بازه به \(y\) تبدیل میشوند.
نوع دوم : یک بازه از دنباله و یک عدد \(k\) داده میشود و میپرسد «اگر تمام بازه را از کوچک به بزرگ مرتب کنیم، عنصر \(k\)ام کدام است؟».
ورودی
در خط اول ورودی دو عدد \(n\)، تعداد اعداد دنباله و \(m\)، تعداد درخواستها، آمدهاست.
در خط دوم \(n\) عدد آمده است که عدد \(i\)ام، \(a_i\)، عدد \(i\)ام دنباله را نشان میدهد.
در \(m\) خط بعدی، در هر خط یک درخواست به یکی از دو شکل زیر آمدهاست:
هر عدد \(x\) در بازه \(l\) تا \(r\) از دنباله (شامل خود آنها) به \(y\) تبدیل میشود.
اگر بازه \(l\) تا \(r\) از دنباله (شامل خود آنها) را از کوچک به بزرگ مرتب کنیم، \(k\)امین عنصر آن را چاپ کنید.
\[1 \le n, m \le 100\ 000\]
\[1 \le a_i \le n\]
\[1 \le l \le r \le n\]
\[1 \le x, y \le n\]
\[1 \le k \le r - l + 1\]
خروجی
به ازای هر درخواست نوع دوم عدد خواسته شده را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۹ | \(1 \le n, m \le 1\ 000\) |
| ۲ | ۲۳ | همه درخواست ها از نوع دوم هستند |
| ۳ | ۶۸ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
7 4
1 2 2 7 3 4 4
1 3 5 2 3
2 1 5 4
1 1 5 7 2
2 4 7 3
خروجی نمونه ۱
3
4
درخواست اول از نوع یک است که در بازه ۳ تا ۵ تمام اعداد ۲ را به ۳ تبدیل میکند.
درخواست دوم چهارمین عدد در حالت مرتب شده ی بازه ۱ تا ۵ را میخواهد. اعداد بازه ۱ تا ۵ به ترتیب ۱ ۲ ۳ ۳ ۷ اند.
درخواست سوم اعداد بازی ۱ تا ۵ که برابر با ۷ اند را به ۲ تغییر میدهد.
و در نهایت درخواست آخر سومین عدد در حالت مرتب شده در بازه ۴ تا ۷ را میخواهد که اعداد این بازه ۲ ۳ ۴ ۴ اند.