CF2111G Divisible Subarrays

本题为交互题。 对于一个长度为 $m$ 的数组 $a$，如果满足以下两个条件之一，则称其为“可分数组”： - 存在一个下标 $i$（$1 \le i < m$）和一个整数 $x$，使得对于所有下标 $j$（$j \le i$），都有 $a_j \le x$，并且对于所有下标 $k$（$k > i$），都有 $a_k > x$。 - 存在一个下标 $i$（$1 \le i < m$）和一个整数 $x$，使得对于所有下标 $j$（$j \le i$），都有 $a_j > x$，并且对于所有下标 $k$（$k > i$），都有 $a_k \le x$。 现在给定一个 $1$ 到 $n$ 的排列 $p$。你需要高效地回答如下询问：对于排列的区间 $[l, r]$，即 $p_l, p_{l+1}, \dots, p_r$，该子数组是否为“可分数组”？ 本题采用交互模式，询问会以每组 $10$ 个的形式给出，只有在输出完当前组所有答案后，才能获得下一组询问。

第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示排列的长度。 第二行包含 $n$ 个整数 $p_i$（$1 \le p_i \le n$），表示排列本身。 第三行包含一个整数 $q$（$10 \le q \le 10^6, q \bmod 10 = 0$），表示询问的数量。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l < r \le n$），表示一次询问的区间参数。

对于每个询问，若该区间对应的子数组为“可分数组”，输出字符串 "YES"；否则输出 "NO"。 每组 $10$ 个询问输出完毕后，需输出换行并刷新输出缓冲区。否则可能会因“空闲限制超时”而被判为错误。刷新缓冲区的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档 你必须在第 $10$、$20$、$30$、…… 个询问（即编号为 $10$ 的倍数的询问）输出后刷新缓冲区，然后才能读取下一组询问。

由 ChatGPT 4.1 翻译