LG#P3901. 数列找不同

数列找不同

P3901 数列找不同

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 qq 次询问。

\hspace{15pt}第 ii 次询问给出一个区间 [li,ri][l_i, r_i],请你判断子数组 {ali,ali+1,…,ari}\{a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\} 内的元素是否两两不同,也就是说,区间内任意两个位置的元素都不相等。

\hspace{15pt}如果互不相同,这次询问的答案为 "Yes"\texttt{"Yes"};否则答案为 "No"\texttt{"No"}。

输入格式

\hspace{15pt}第一行输入两个整数 n,q(1≦n,q≦105)n, q \left(1 \leqq n, q \leqq 10^5\right) 代表数列长度和询问次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq n\right)$ 代表数列中的元素。

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

输出格式

\hspace{15pt}输出 qq 行,第 ii 行输出一个字符串,代表第 ii 次询问的答案。若区间 [li,ri][l_i, r_i] 内的元素两两不同,输出 "Yes"\texttt{"Yes"};否则输出 "No"\texttt{"No"}。

测试样例

4 2
1 2 3 2
1 3
2 4
Yes
No

样例 1 解释

\hspace{15pt}数列为 {1,2,3,2}\{1, 2, 3, 2\},共有 22 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [1,3][1, 3],对应子数组 {1,2,3}\{1, 2, 3\},三个元素互不相同,输出 "Yes"\texttt{"Yes"};

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [2,4][2, 4],对应子数组 {2,3,2}\{2, 3, 2\},其中 22 出现了两次,输出 "No"\texttt{"No"}。

8 3
5 3 5 3 7 3 5 3
1 2
1 4
7 8
Yes
No
Yes

样例 2 解释

\hspace{15pt}数列为 {5,3,5,3,7,3,5,3}\{5, 3, 5, 3, 7, 3, 5, 3\},共有 33 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [1,2][1, 2],对应子数组 {5,3}\{5, 3\},两个元素互不相同,输出 "Yes"\texttt{"Yes"};

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [1,4][1, 4],对应子数组 {5,3,5,3}\{5, 3, 5, 3\},其中 55 和 33 都出现了两次,输出 "No"\texttt{"No"};

∙ \hspace{23pt}\bullet\,第 33 次询问的区间为 [7,8][7, 8],对应子数组 {5,3}\{5, 3\},两个元素互不相同,输出 "Yes"\texttt{"Yes"}。

提示

\hspace{15pt}对于 50%50\% 的数据,1≦n,q≦1031 \leqq n, q \leqq 10^3。

\hspace{15pt}对于 100%100\% 的数据,1≦n,q≦1051 \leqq n, q \leqq 10^5,1≦ai≦n1 \leqq a_i \leqq n,1≦li≦ri≦n1 \leqq l_i \leqq r_i \leqq n。