فهرست مندرجات
Permutation
به شما جایگشت $p$ از اعداد $1$ تا $n$ داده شده است، شما باید تعداد $1 \leq i \leq j \leq n$ هایی را بیابید که اعداد $p_i$ تا $p_j$ یک بازه پشت‌سرهم از اعداد را تشکیل می‌دهد. برای مثال پاسخ سوال برای جایگشت $<1,3,2,4>$ جفت $i$ و $j$های زیر است:
- $(1,1)$
- $(2,2)$
- $(3,3)$
- $(4,4)$
- $(1,3)$
- $(1,4)$
- $(2,4)$
- $(2,3)$
ورودی
- در سطر اول ورودی، عدد $1 \leq n \leq 5000$ آمده است.
- در سطر بعدی، اعداد $p_1$ تا $p_n$ آمده‌اند.
خروجی
در تنها سطر خروجی تعداد $(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$ در یک بازه قرار دارند، پس شرط زیر بر قرار است:
- $max(p_i,p_{i+1},\cdots,p_j) - min(p_i,p_{i+1},\cdots,p_j) = j-i$
می‌توان نشان داد که اگر یک بازه $(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)$ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
