Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۳۸

Segment Tree

یک دنباله n تایی از اعداد داریم. در هر مرحله یک بازه متوالی از این دنباله را انتخاب کرده و ماکسیمم آن را به‌دست می‌آوریم. بعد تمام اعداد بازه را برابر ماکسیمم قرار می‌دهیم. هم‌چنین اگر تمام اعداد بازه برابر ماکسیمم بودند به همه یک واحد اضافه می‌کنیم.

ورودی

  • در خط اول دو عدد n و q آمده است.
  • در خط دوم n عدد آمده که نمایانگر اعداد اولیه دنباله‌اند. (تمام اعداد این خط بین 0 و109 اند)
  • در q خط بعد در هر خط دو عدد L و R آمده است که به معنی انتخاب بازه‌ی [L, R] است.
  • 1n,q105

خروجی

به ازای هر یک از q مرحله، در یک خط تعداد اعدادی که مقدارشان تغییر کرده‌است را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5 4
1 2 3 2 1
1 1
1 2
1 5
1 5
1
2
2
5

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه