CF2111G.Divisible Subarrays

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

本题为交互题。

对于一个长度为 $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$ 个询问输出完毕后，需输出换行并刷新输出缓冲区。否则可能会因“空闲限制超时”而被判为错误。刷新缓冲区的方法如下：

你必须在第 $10$ 、 $20$ 、 $30$ 、…… 个询问（即编号为 $10$ 的倍数的询问）输出后刷新缓冲区，然后才能读取下一组询问。

输入#1

7
4 2 3 6 1 5 7
20
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
2 7
3 7
4 7
5 7

输出#1

YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?