← 返回题目列表

Codeforces · 1997/E

E. 升级

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

Monocarp 正在玩电脑游戏。他开始游戏时的等级是$$$1$$$。他即将与 $$$n$$$ 个怪物战斗,顺序为 $$$1$$$ 到 $$$n$$$。第$$$i$$$个怪物的等级为$$$a_i$$$。

对于给定顺序中的每个怪物,Monocarp 的遭遇如下:

- 如果Monocarp的等级严格高于怪物的等级,则怪物逃跑(逃跑);
- 否则,Monocarp 会与怪物战斗。

在与怪物每 $$$k$$$ 次战斗后(逃跑的怪物不计算在内),Monocarp 的等级会增加 $$$1$$$。因此,在与$$$k$$$怪物战斗后,他的等级变为$$$2$$$,在与$$$2k$$$怪物战斗后,他的等级变为$$$3$$$,在与$$$3k$$$怪物战斗后,他的等级变为$$$4$$$,依此类推。

您需要处理以下形式的 $$$q$$$ 查询:

- $$$i~x$$$:如果参数 $$$k$$$ 等于 $$$x$$$,Monocarp 会与第 $$$i$$$ 个怪物战斗(或者该怪物会逃跑)吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — 怪物数量和查询数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 怪物的等级。

在以下 $$$q$$$ 行的第 $$$j$$$ 行中,两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i, x \le n$$$) — 怪物的索引以及第 $$$j$$$ 查询中升级所需的战斗次数。

输出

对于每个查询,如果 Monocarp 将与该查询中的第 $$$i$$$ 个怪物战斗,则输出“YES”;如果第 $$$i$$$ 个怪物逃跑,则输出“NO”。

示例

输入 #1

4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4

输出 #1

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

输入 #2

7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1

输出 #2

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