← 返回题目列表

Codeforces · 2014/H

H. 罗宾汉射箭

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

诺丁汉警长组织了一场射箭比赛。最后一轮是罗宾汉对阵警长!

一行中有 $$$n$$$ 个目标,编号从 $$$1$$$ 到 $$$n$$$。当玩家射击目标 $$$i$$$ 时,他们的分数会增加 $$$a_i$$$ 并且目标 $$$i$$$ 被摧毁。游戏由回合组成,玩家轮流轮流进行。罗宾汉总是先开始游戏,然后是警长,依此类推。游戏继续进行,直到所有目标都被摧毁。两名玩家的起始得分均为 $$$0$$$。

游戏结束时,得分最多的玩家获胜,另一位玩家失败。如果两名玩家得分相同,则为平局,没有人获胜或失败。在每个回合中,玩家可以射击任何之前未射击过的目标。两者都以最佳方式发挥以获得尽可能高的分数。

诺丁汉警长怀疑自己可能会输掉比赛!这不可能发生,你必须帮助警长。治安官将提出 $$$q$$$ 查询,每个查询指定 $$$l$$$ 和 $$$r$$$。这意味着游戏将仅使用目标 $$$l、l+1、\dots、r$$$ 进行,因为其他目标将在游戏开始前被 Sheriff 删除。

对于每个查询 $$$l$$$, $$$r$$$,确定 Sheriff 在仅考虑目标 $$$l, l+1, \dots, r$$$ 时是否不会输掉比赛。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \le n,q \le 2\cdot10^5$$$) - 目标数量和警长将提出的查询。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 击中每个目标的点。

然后跟随 $$$q$$$ 行,每行有两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 每个查询考虑的目标范围。

保证所有测试用例中的 $$$n$$$ 和 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,如果警长在仅考虑目标 $$$l、l+1、\dots、r$$$ 时没有输掉比赛,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

2
3 3
1 2 2
1 2
1 3
2 3
5 3
2 1 2 1 1
1 2
1 3
4 5

输出 #1

NO
NO
YES
NO
NO
YES