← 返回题目列表

Codeforces · 2111/G

G. 可除子数组

中文机器翻译题面 查看原题

从技术上讲,这是一个交互问题。

一个包含 $$$m$$$ 数字的数组 $$$a$$$ 被称为 可整除 如果至少满足以下条件之一:

  • 存在一个索引 $$$i$$$ ($$$1 \le i \lt m$$$) 和一个整数 $$$x$$$,这样对于所有索引 $$$j$$$ ($$$j \le i$$$),它认为 $$$a_{j} \le x$$$ 对于所有索引 $$$k$$$ ($$$k \gt i$$$),它认为$$$a_{k} \gt x$$$。
  • 存在一个索引 $$$i$$$ ($$$1 \le i \lt m$$$) 和一个整数 $$$x$$$,这样对于所有索引 $$$j$$$ ($$$j \le i$$$),它保持 $$$a_{j} \gt x$$$ 并且对于所有索引 $$$k$$$ ($$$k \gt i$$$),它保持$$$a_{k} \le x$$$。

给你一个整数 $$$1, 2, \dots, n$$$ 的排列 $$$p$$$。你的任务是快速回答以下形式的查询:如果我们只从排列中取出段 [$$$l$$$, $$$r$$$],即数字 $$$p_{l}, p_{l + 1}, \dots, p_{r}$$$,就是这个数字子数组 可整除?

查询将以交互模式以 $$$10$$$ 为一组提交,这意味着在输出当前组的所有答案之前,您将不会收到下一组查询。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 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 \lt r \le n$$$) — 查询的参数。

输出

对于每个查询,输出字符串“是"如果此查询的子数组是 可整除 和“NO”否则。

打印一组查询的答案后,不要忘记输出行尾并刷新输出缓冲区。否则,您可能会得到 超出空闲限制 判决。要刷新缓冲区,请使用:

  • fflush(标准输出) or cout.flush() in C++;
  • System.out.flush() in Java;
  • 冲洗(输出) in 帕斯卡;
  • stdout.flush() in Python;
  • 请参阅其他语言的文档。

您必须在第 $$$10$$$、第 $$$20$$$、第 $$$30$$$ 查询(依此类推)之后刷新输出缓冲区,i。 e.在索引可被 $$$10$$$ 整除的每个查询之后。之后,您可以阅读下一组查询。

示例

输入
复制

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

输出
复制

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