المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۴:سوال ۴

Deployment

همان‌طور که از اسم گروه‌های نظامی پیدا است، نظم یکی از ارکان مهم چنین گروه‌هایی است به طوری که حتی ترتیب قرار گرفتن افراد در صف هم اهمیت دارد. برای ارزیابی نظم یک صف، «نظریه‌ی صف‌ها» مطرح شده که به بعضی از تعاریف آن در ادامه‌ی سوال اشاره شده است.

  • منظور از زیر صف $[l,r]$ از صف $q$، صفی شامل افراد $l$- ام تا $r$- ام از $q$ با همان ترتیب اولیه است. در واقع زیر صف $[l,r]$، صفی به طول $r-l+1$ است.
  • اگر دنباله‌ی قد افراد یک صف (بر حسب نانومتر) را $h_1,h_2,…,h_n$ در نظر بگیرید، رتبه‌ی صف برابر است با طول بزرگ‌ترین (بر حسب الفبایی) زیردنباله‌ی نه لزوما متوالی از دنباله‌ی $h$.
  • نظام‌مندی یک صف نیز برابر است با مجموع رتبه‌ی تمامی زیرصف‌های آن. دقت کنید که تعداد زیرصف‌های یک صف به طول $l$ برابر با $\frac{l\times (l+1)}{2}$ است.

شما باید با گرفتن دنباله‌ی قد افراد یک صف، به پرسش‌های به شکل «نظام‌مندی زیرصف $[l,r]$ چقدر است؟» پاسخ دهید.

ورودی

سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد افراد صف و $k$، تعداد پرسش‌ها، است.($1\leq n,k \leq 3\times 10^5$)

سطر دوم شامل دنباله‌ی $h_1,h_2,…,h_n$ است که قد افراد صف را بر حسب نانومتر نشان می‌دهد.($1\leq h_i \leq 10^9$)

در هر یک از $k$ سطر بعدی به ترتیب دو عدد طبیعی $l$ و $r$ آمده است.($1\leq l \leq r \leq n$)

خروجی

خروجی باید شامل $k$ سطر باشد که در سطر $i$ ام از آن، پاسخ به پرسش شماره‌ی $i$ آمده است.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2 1
2 1
1 2
4
5 4
2 3 1 4 5
1 4
2 5
3 5
1 5
12
11
6
17

ابزار صفحه