Харагдах барилгуудын хүсэлтүүд

2s

512MB

1450

0%

Range Queries

$n$ барилга нэг эгнээнд зүүнээс баруун тийш $1, 2,\dots, n$ гэж дугаарлагдсан. Та эхний барилгын зүүн талд зогсож байна. Барилга нь өөрөөс нь зүүн талын бүх барилгаас өндөр бол харагдана.

$q$ хүсэлтүүдийг боловсруул: зөвхөн $[a, b]$ мужийн барилгууд оршин байсан бол хэдэн барилга харагдах вэ?

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

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

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

Хоёр дахь мөрөнд $n$ бүхэл тоо $h_1, h_2, \dots, h_n$ байна: барилгуудын өндөр.

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

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

Хүсэлт бүрт нэг бүхэл тоо хэвлэ: харагдах барилгуудын тоо.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le q \le 2 \cdot 10^5$
$1 \le h_i \le 10^9$
$1 \le a \le b \le n$

Жишээ

Оролт1

Гаралт1

1
3
1

0.1 / 64 KiB

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