CF2014H Robin Hood Archery
题目描述
诺丁汉郡长组织了一场射箭比赛。这是最后一轮,罗宾汉对阵郡长。
编号为 1 到 n 的位置上依次立着 n 个目标,第 i 个目标的价值为 ai。当一名玩家射中目标 i 时,他的得分增加 ai,这个目标随即被摧毁,之后任何人都不能再射击它。
游戏由若干回合组成,两名玩家轮流行动:罗宾汉先行动,接下来是郡长,然后又是罗宾汉,如此交替。每一回合,当前行动的玩家必须射中一个尚未被摧毁的目标。当所有目标都被摧毁时,游戏结束。此时得分较多的玩家获胜,另一名玩家落败;如果双方得分相同,则为平局,没有人获胜,也没有人落败。
两名玩家都足够聪明,都会采取最优策略,使自己的得分尽可能高。
郡长担心自己会输掉比赛。他会提出 q 个查询,第 t 个查询给出两个整数 lt 和 rt,表示游戏开始前只保留编号在 lt 到 rt 之间的目标,其余目标都被移除,游戏只在剩下的目标上进行。对于每个查询,请判断在双方都采取最优策略时,郡长是否会输掉比赛。
输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦104) 代表数据组数,每组测试数据描述如下:
每组测试数据的第一行输入两个整数 n,q(1≦n,q≦2×105) 代表目标的数量和查询次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表每个目标的价值。
此后 q 行,第 i 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 i 个查询保留的目标区间。
除此之外,保证单个测试文件的 n 之和不超过 2×105,q 之和也不超过 2×105。
输出格式
对于每个查询,输出一行:如果郡长不会输掉比赛,输出 "YES";否则输出 "NO"。
所有测试数据的答案按查询给出的顺序依次输出。
测试样例
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 解释
样例共有两组测试数据。
第一组测试数据中,n=3,a={1,2,2}。
∙查询 [1,2]:只剩目标 {1,2}。罗宾汉射中价值为 2 的目标,郡长只能射中价值为 1 的目标,最终比分为 2:1,郡长输掉比赛,输出 "NO";
∙查询 [1,3]:目标为 {1,2,2}。罗宾汉射中一个价值为 2 的目标,郡长射中另一个价值为 2 的目标,最后罗宾汉射中价值为 1 的目标,最终比分为 3:2,郡长输掉比赛,输出 "NO";
∙查询 [2,3]:只剩目标 {2,2}。两人各射中一个价值为 2 的目标,最终比分为 2:2,双方平局,郡长不输,输出 "YES"。
第二组测试数据中,n=5,a={2,1,2,1,1}。
∙查询 [1,2]:只剩目标 {2,1}。罗宾汉射中价值为 2 的目标,郡长射中价值为 1 的目标,最终比分为 2:1,输出 "NO";
∙查询 [1,3]:目标为 {2,1,2}。罗宾汉射中一个价值为 2 的目标,郡长射中另一个价值为 2 的目标,最后罗宾汉射中价值为 1 的目标,最终比分为 3:2,输出 "NO";
∙查询 [4,5]:只剩目标 {1,1}。两人各射中一个价值为 1 的目标,最终比分为 1:1,输出 "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 解释
第一组测试数据中,n=6,a={3,1,3,1,2,2}。
∙查询 [1,6]:罗宾汉与郡长依次射中价值为 3,3,2,2,1,1 的目标,最终比分为 6:6,双方平局,输出 "YES";
∙查询 [1,2]:只剩目标 {3,1},罗宾汉射中价值为 3 的目标,郡长射中价值为 1 的目标,最终比分为 3:1,输出 "NO";
∙查询 [3,6]:目标为 {3,1,2,2},罗宾汉依次射中价值为 3 和 2 的目标,郡长依次射中价值为 2 和 1 的目标,最终比分为 5:3,输出 "NO"。
第二组测试数据中,n=5,a={2,2,2,2,2}。
∙查询 [1,4]:四个目标的价值都是 2,两人各射中两个,最终比分为 4:4,输出 "YES";
∙查询 [1,5]:五个目标的价值都是 2,罗宾汉射中三个、郡长射中两个,最终比分为 6:4,输出 "NO";
∙查询 [2,5]:四个目标的价值都是 2,两人各射中两个,最终比分为 4:4,输出 "YES"。