Visible Buildings Queries

题目描述

有 n 棟建築物按從左到右的順序編號為 1, 2,$\dots$, n。你站在第一棟建築物的左側。若某棟建築物比它左邊的所有建築物都要高，則你可以看到該建築物。 你的任務是處理 q 個查詢：若僅存在區間 [a, b] 內的建築物，則你會看到多少棟建築物？

输入格式

第一行有兩個整數 n 和 q：建築物的數量與查詢數量。 第二行有 n 個整數 $h_1$, $h_2$, $\dots$, $h_n$：建築物的高度。 最後有 q 行描述查詢。每行有兩個整數 a 和 b。

输出格式

對於每個查詢，輸出一個整數：可見的建築物數量。

5 3
4 1 2 2 3
1 5
2 5
3 4

1
3
1

提示

$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$

标签: CSES3304|区间查询

来源

CSES3304|区间查询