P3901 数列找不同
题目描述
给定一个长度为 n 的整数数列 {a1,a2,…,an},以及 q 次询问。
第 i 次询问给出一个区间 [li,ri],请你判断子数组 {ali,ali+1,…,ari} 内的元素是否两两不同,也就是说,区间内任意两个位置的元素都不相等。
如果互不相同,这次询问的答案为 "Yes";否则答案为 "No"。
输入格式
第一行输入两个整数 n,q(1≦n,q≦105) 代表数列长度和询问次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq n\right)$ 代表数列中的元素。
此后 q 行,第 i 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 i 次询问的区间。
输出格式
输出 q 行,第 i 行输出一个字符串,代表第 i 次询问的答案。若区间 [li,ri] 内的元素两两不同,输出 "Yes";否则输出 "No"。
测试样例
4 2
1 2 3 2
1 3
2 4
Yes
No
样例 1 解释
数列为 {1,2,3,2},共有 2 次询问。
∙第 1 次询问的区间为 [1,3],对应子数组 {1,2,3},三个元素互不相同,输出 "Yes";
∙第 2 次询问的区间为 [2,4],对应子数组 {2,3,2},其中 2 出现了两次,输出 "No"。
8 3
5 3 5 3 7 3 5 3
1 2
1 4
7 8
Yes
No
Yes
样例 2 解释
数列为 {5,3,5,3,7,3,5,3},共有 3 次询问。
∙第 1 次询问的区间为 [1,2],对应子数组 {5,3},两个元素互不相同,输出 "Yes";
∙第 2 次询问的区间为 [1,4],对应子数组 {5,3,5,3},其中 5 和 3 都出现了两次,输出 "No";
∙第 3 次询问的区间为 [7,8],对应子数组 {5,3},两个元素互不相同,输出 "Yes"。
提示
对于 50% 的数据,1≦n,q≦103。
对于 100% 的数据,1≦n,q≦105,1≦ai≦n,1≦li≦ri≦n。