#CF2014H. 罗宾汉的射箭比赛

罗宾汉的射箭比赛

CF2014H Robin Hood Archery

题目描述

\hspace{15pt}诺丁汉郡长组织了一场射箭比赛。这是最后一轮,罗宾汉对阵郡长。

\hspace{15pt}编号为 11 到 nn 的位置上依次立着 nn 个目标,第 ii 个目标的价值为 aia_i。当一名玩家射中目标 ii 时,他的得分增加 aia_i,这个目标随即被摧毁,之后任何人都不能再射击它。

\hspace{15pt}游戏由若干回合组成,两名玩家轮流行动:罗宾汉先行动,接下来是郡长,然后又是罗宾汉,如此交替。每一回合,当前行动的玩家必须射中一个尚未被摧毁的目标。当所有目标都被摧毁时,游戏结束。此时得分较多的玩家获胜,另一名玩家落败;如果双方得分相同,则为平局,没有人获胜,也没有人落败。

\hspace{15pt}两名玩家都足够聪明,都会采取最优策略,使自己的得分尽可能高。

\hspace{15pt}郡长担心自己会输掉比赛。他会提出 qq 个查询,第 tt 个查询给出两个整数 ltl_t 和 rtr_t,表示游戏开始前只保留编号在 ltl_t 到 rtr_t 之间的目标,其余目标都被移除,游戏只在剩下的目标上进行。对于每个查询,请判断在双方都采取最优策略时,郡长是否会输掉比赛。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦104)t \left(1 \leqq t \leqq 10^4\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}每组测试数据的第一行输入两个整数 n,q(1≦n,q≦2×105)n, q \left(1 \leqq n, q \leqq 2 \times 10^5\right) 代表目标的数量和查询次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表每个目标的价值。

\hspace{15pt}此后 qq 行,第 ii 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 ii 个查询保留的目标区间。

\hspace{15pt}除此之外,保证单个测试文件的 nn 之和不超过 2×1052 \times 10^5,qq 之和也不超过 2×1052 \times 10^5。

输出格式

\hspace{15pt}对于每个查询,输出一行:如果郡长不会输掉比赛,输出 "YES"\texttt{"YES"};否则输出 "NO"\texttt{"NO"}。

\hspace{15pt}所有测试数据的答案按查询给出的顺序依次输出。

测试样例

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
NO
NO
YES
NO
NO
YES

样例 1 解释

\hspace{15pt}样例共有两组测试数据。

\hspace{15pt}第一组测试数据中,n=3n = 3,a={1,2,2}a = \{1, 2, 2\}。

∙ \hspace{23pt}\bullet\,查询 [1,2][1, 2]:只剩目标 {1,2}\{1, 2\}。罗宾汉射中价值为 22 的目标,郡长只能射中价值为 11 的目标,最终比分为 2:12 : 1,郡长输掉比赛,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [1,3][1, 3]:目标为 {1,2,2}\{1, 2, 2\}。罗宾汉射中一个价值为 22 的目标,郡长射中另一个价值为 22 的目标,最后罗宾汉射中价值为 11 的目标,最终比分为 3:23 : 2,郡长输掉比赛,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [2,3][2, 3]:只剩目标 {2,2}\{2, 2\}。两人各射中一个价值为 22 的目标,最终比分为 2:22 : 2,双方平局,郡长不输,输出 "YES"\texttt{"YES"}。

\hspace{15pt}第二组测试数据中,n=5n = 5,a={2,1,2,1,1}a = \{2, 1, 2, 1, 1\}。

∙ \hspace{23pt}\bullet\,查询 [1,2][1, 2]:只剩目标 {2,1}\{2, 1\}。罗宾汉射中价值为 22 的目标,郡长射中价值为 11 的目标,最终比分为 2:12 : 1,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [1,3][1, 3]:目标为 {2,1,2}\{2, 1, 2\}。罗宾汉射中一个价值为 22 的目标,郡长射中另一个价值为 22 的目标,最后罗宾汉射中价值为 11 的目标,最终比分为 3:23 : 2,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [4,5][4, 5]:只剩目标 {1,1}\{1, 1\}。两人各射中一个价值为 11 的目标,最终比分为 1:11 : 1,输出 "YES"\texttt{"YES"}。

2
6 3
3 1 3 1 2 2
1 6
1 2
3 6
5 3
2 2 2 2 2
1 4
1 5
2 5
YES
NO
NO
YES
NO
YES

样例 2 解释

\hspace{15pt}第一组测试数据中,n=6n = 6,a={3,1,3,1,2,2}a = \{3, 1, 3, 1, 2, 2\}。

∙ \hspace{23pt}\bullet\,查询 [1,6][1, 6]:罗宾汉与郡长依次射中价值为 3,3,2,2,1,13, 3, 2, 2, 1, 1 的目标,最终比分为 6:66 : 6,双方平局,输出 "YES"\texttt{"YES"};

∙ \hspace{23pt}\bullet\,查询 [1,2][1, 2]:只剩目标 {3,1}\{3, 1\},罗宾汉射中价值为 33 的目标,郡长射中价值为 11 的目标,最终比分为 3:13 : 1,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [3,6][3, 6]:目标为 {3,1,2,2}\{3, 1, 2, 2\},罗宾汉依次射中价值为 33 和 22 的目标,郡长依次射中价值为 22 和 11 的目标,最终比分为 5:35 : 3,输出 "NO"\texttt{"NO"}。

\hspace{15pt}第二组测试数据中,n=5n = 5,a={2,2,2,2,2}a = \{2, 2, 2, 2, 2\}。

∙ \hspace{23pt}\bullet\,查询 [1,4][1, 4]:四个目标的价值都是 22,两人各射中两个,最终比分为 4:44 : 4,输出 "YES"\texttt{"YES"};

∙ \hspace{23pt}\bullet\,查询 [1,5][1, 5]:五个目标的价值都是 22,罗宾汉射中三个、郡长射中两个,最终比分为 6:46 : 4,输出 "NO"\texttt{"NO"};

∙ \hspace{23pt}\bullet\,查询 [2,5][2, 5]:四个目标的价值都是 22,两人各射中两个,最终比分为 4:44 : 4,输出 "YES"\texttt{"YES"}。