Segment Tree
یک دنباله n تایی از اعداد داریم. در هر مرحله یک بازه متوالی از این دنباله را انتخاب کرده و ماکسیمم آن را بهدست میآوریم. بعد تمام اعداد بازه را برابر ماکسیمم قرار میدهیم. همچنین اگر تمام اعداد بازه برابر ماکسیمم بودند به همه یک واحد اضافه میکنیم.
ورودی
در خط اول دو عدد n و q آمده است.
در خط دوم n عدد آمده که نمایانگر اعداد اولیه دنبالهاند. (تمام اعداد این خط بین 0 و109 اند)
در q خط بعد در هر خط دو عدد L و R آمده است که به معنی انتخاب بازهی [L, R] است.
1≤n,q≤105
خروجی
به ازای هر یک از q مرحله، در یک خط تعداد اعدادی که مقدارشان تغییر کردهاست را بنویسید.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
5 4
1 2 3 2 1
1 1
1 2
1 5
1 5 | 1
2
2
5 |
پاسخ
منتظر پر کردن این قسمت توسط علاقمندان هستیم.