به شما جایگشت $p$ از اعداد $1$ تا $n$ داده شده است، شما باید تعداد $1 \leq i \leq j \leq n$ هایی را بیابید که اعداد $p_i$ تا $p_j$ یک بازه پشت‌سرهم از اعداد را تشکیل می‌دهد. برای مثال پاسخ سوال برای جایگشت $<1,3,2,4>$ جفت $i$ و $j$های زیر است:
در تنها سطر خروجی تعداد $(i,j)$های مورد نظر را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 4 1 3 2 4 | 8 |
| 5 1 2 3 4 5 | 15 |
پاسخ
فرض کنید بازه $(i,j)$ یکی از بازه‌های مورد نظر ما باشد. چون تمام اعداد $p_i$ ، $p_{i+1}$ ، $\cdots$ ، $p_j$ در یک بازه قرار دارند، پس شرط زیر بر قرار است:
می‌توان نشان داد که اگر یک بازه $(i,j)$ شرط بالا را داشته باشد، اعداد $p_i$ تا $p_j$ در یک بازه قرار خواهند داشت.
پس کافیست تعداد $(i,j)$ هایی را بشماریم که شرط بالا را دارند.
برای این کار می‌توان min[i][j] و max[i][j] را برای همه اعداد $1$ تا $n$ به صورت پویا به‌دست بیاوریم و شرط گفته شده را برای تمام بازه‌ها چک کنیم.
پیچیدگی
ساختن آریه min و max را می‌توان در زمان $o(n^2)$ انجام داد و چک کردن هر بازه در زمان $o(1)$ انجام می‌شود. پس می‌توان همه بازه‌ها را در زمان $o(n^2)$ چک کرد.
پیچیدگی زمانی الگوریتم گفته شده برابر با $o(n^2)$ است.