Өсөх массивын хүсэлтүүд

2s

512MB

1525

0%

Range Queries

$n$ бүхэл тооноос бүрдсэн массив өгөгдсөн. Элементүүдийг $1,2,\dots,n$ гэж дугаарласан.

Массивыг дараах үйлдлээр өөрчилж болно: массивын элемент сонгоод утгыг нь нэгээр нэмэх.

Дараах хэлбэрийн $q$ хүсэлтүүдийг боловсруул: $a$ байрлалаас $b$ байрлал хүртэлх дэд хэсгийг авбал түүнийг өсөх болгож чадах хамгийн бага үйлдлийн тоо юу вэ?

Массив өсөх гэдэг нь элемент бүр өмнөх элементээсээ их буюу тэнцүү байхыг хэлнэ.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $q$ байна: массивын хэмжээ ба хүсэлтийн тоо.

Хоёр дахь мөрөнд $n$ бүхэл тоо $x_1,x_2,\dots,x_n$ байна: массивын агуулга.

Эцэст нь $q$ мөрөнд хүсэлтүүд байна. Мөр бүрт хоёр бүхэл тоо $a$ ба $b$ : дэд хэсгийн эхлэх ба дуусах байрлал.

Гаралтын формат

Хүсэлт бүрт хамгийн бага үйлдлийн тоог хэвлэ.

Хязгаарлалт

$1 \le n,q \le 2\cdot10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Жишээ

Оролт1

Гаралт1

2
0
14

0.1 / 64 KiB

Редактор уншиж байна...