CF279C Ladder

你有一个由 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ 组成的数组。同时，你有 $m$ 个询问，第 $i$ 个询问由两个整数 $l_{i}, r_{i}$ 描述。数字 $l_{i}, r_{i}$ 定义了原数组的一个子区间，即由 $a_{l_i}, a_{l_i+1}, a_{l_i+2}, ..., a_{r_i}$ 组成的序列。对于每个询问，你需要判断对应的区间是否是一个梯子（ladder）。 一个梯子是指这样一个整数序列 $b_{1},b_{2},...,b_{k}$，它先不下降，然后不上升。换句话说，存在一个整数 $x$ $(1 \leq x \leq k)$，使得下式成立：$b_{1} \leq b_{2} \leq ... \leq b_{x} \geq b_{x+1} \geq b_{x+2} ... \geq b_{k}$。需要注意的是，单调不下降或单调不升的序列也被认为是梯子。

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 10^{5})$，分别表示数组元素个数和询问数量。第二行包含 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$ $(1 \leq a_{i} \leq 10^{9})$，其中 $a_{i}$ 表示第 $i$ 个数组元素。 接下来的 $m$ 行描述了每个询问。第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq n)$，表示初始数组的子区间的左右边界。 每行中的数字之间用一个空格隔开。

输出 $m$ 行，对于第 $i$ 个询问，如果对应的子区间是一个梯子，则输出 "Yes"（不带引号），否则输出 "No"（不带引号）。

由 ChatGPT 5 翻译