Diverse Segments

题意翻译

### 题目描述 给定长度为 $n$ 的序列 $a$，以及 $m$ 个数对 $(l_i,r_i)$。 你可以进行下列操作至多一次： - 选择序列 $a$ 的一个子段，并将其中的每个元素的值都改成任意整数。 你需要保证执行完操作之后，对于每个整数 $i(1\leq i\leq m)$，都有 $a[l_i,r_i]$ 中所有元素互不相同。 你需要最小化操作时选择的子段的长度，并求出这个长度的最小值。 特别的如果没有必要进行操作，答案为 $0$。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq100)$ 表示数据组数，接下来对于每组数据： 第一行输入两个整数 $n,m(1\leq n,m,\sum n,\sum m\leq2\times10^5)$ 表示序列长度和给定的数对数。 接下来一行输入 $n$ 个整数表示 $a_1,a_2,\cdots,a_n(1\leq a_i\leq10^9)$。 接下来输入 $m$ 行，其中第 $i$ 行输入两个整数表示 $l_i,r_i(1\leq l_i\leq r_i\leq n)$。 ### 输出格式 对于每组数据： 输出进行操作的子段的长度的最小值。 ### 样例解释 对于第一组数据，我们可以选择子段 $[1,2]$ 并将序列改成 $[114,514,2,1,3,3,5]$，此时： - 对于第一个数对 $(1,4)$，我们有 $a[1,4]=[114,514,2,1]$。 - 对于第二个数对 $(4,5)$，我们有 $a[4,5]=[1,3]$。 - 对于第三个数对 $(2,4)$，我们有 $a[2,4]=[514,2,1]$。 显然每个数对都满足要求，且我们可以证明没有更优的答案，因此答案为 $2$。 对于第二组数据，我们没有必要进行操作。 对于第三组数据，我们可以选择子段 $[1,1]$ 并将序列改成 $[1,7,5,6]$。

题目描述

You are given an array $ a $ of $ n $ integers. Also you are given $ m $ subsegments of that array. The left and the right endpoints of the $ j $ -th segment are $ l_j $ and $ r_j $ respectively. You are allowed to make no more than one operation. In that operation you choose any subsegment of the array $ a $ and replace each value on this segment with any integer (you are also allowed to keep elements the same). You have to apply this operation so that for the given $ m $ segments, the elements on each segment are distinct. More formally, for each $ 1 \le j \le m $ all elements $ a_{l_{j}}, a_{l_{j}+1}, \ldots, a_{r_{j}-1}, a_{r_{j}} $ should be distinct. You don't want to use the operation on a big segment, so you have to find the smallest length of a segment, so that you can apply the operation to this segment and meet the above-mentioned conditions. If it is not needed to use this operation, the answer is $ 0 $ .

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 2 \cdot 10^5 $ ) — the size of the array and the number of segments respectively. The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of $ a $ . Each of the next $ m $ lines contains two integers $ l_j $ , $ r_j $ ( $ 1 \le l_j \le r_j \le n $ ) — the left and the right endpoints of the $ j $ -th segment. It's guaranteed that the sum of $ n $ and the sum of $ m $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output a single integer — the smallest length of a segment you can apply an operation on making the elements on all given segments distinct. If it is not needed to use the operation, output $ 0 $ .

输入输出样例

输入样例 #1

5
7 3
1 1 2 1 3 3 5
1 4
4 5
2 4
5 2
10 1 6 14 1
4 5
2 4
4 5
5 7 5 6
2 2
1 3
2 4
3 3
3 4
7 3
2 2 2 7 8 2 2
4 4
4 4
5 5
1 1
123
1 1

输出样例 #1

2
0
1
0
0

说明

In the first test case you can perform the operation on the segment $ [1, 2] $ and make $ a = [5, 6, 2, 1, 3, 3, 5] $ . Then the elements on each segment are distinct. - On the segment $ [1, 4] $ there are $ [5, 6, 2, 1] $ . - On the segment $ [4, 5] $ there are $ [1, 3] $ . - On the segment $ [2, 4] $ there are $ [6, 2, 1, 3] $ . This way on each of the given segments all elements are distinct. Also, it is impossible to change any single integer to make elements distinct on each segment. That is why the answer is $ 2 $ . In the second test case the elements on each segment are already distinct, so we should not perform the operation. In the third test case we can replace the first $ 5 $ by $ 1 $ . This way we will get $ [1, 7, 5, 6] $ where all elements are distinct so on each given segment all elements are distinct.

**题目大意：**

给定一个长度为 $ n $ 的整数序列 $ a $ 和 $ m $ 个数对 $(l_i,r_i)$，你可以选择序列 $ a $ 的一个子段，并改变这个子段内每个元素的值。你的目标是通过这一操作使得对于每个 $ i(1\leq i\leq m) $，序列 $ a[l_i,r_i] $ 中的所有元素都是唯一的。如果没有必要进行这个操作，答案为 $ 0 $。求进行操作时选择的子段的最小长度。

**输入数据格式：**

- 第一行输入一个整数 $ t(1\leq t\leq100) $ 表示数据组数。
- 每组数据：
- 第一行输入两个整数 $ n,m(1\leq n,m,\sum n,\sum m\leq2\times10^5) $，分别表示序列长度和给定的数对数。
- 接下来一行输入 $ n $ 个整数表示序列 $ a_1,a_2,\cdots,a_n(1\leq a_i\leq10^9) $。
- 接下来输入 $ m $ 行，每行输入两个整数表示数对 $ l_i,r_i(1\leq l_i\leq r_i\leq n) $。

**输出数据格式：**

- 对于每组数据，输出进行操作时选择的子段的最小长度。如果没有必要进行操作，输出 $ 0 $。

**样例解释：**

- 第一组数据，可以选择子段 $[1,2]$ 并将序列改成 $[5,6,2,1,3,3,5]$，此时每个数对都满足要求，且没有更优的答案，因此答案为 $ 2 $。
- 第二组数据，没有必要进行操作。
- 第三组数据，可以选择子段 $[1,1]$ 并将序列改成 $[1,7,5,6]$。**题目大意：** 给定一个长度为 $ n $ 的整数序列 $ a $ 和 $ m $ 个数对 $(l_i,r_i)$，你可以选择序列 $ a $ 的一个子段，并改变这个子段内每个元素的值。你的目标是通过这一操作使得对于每个 $ i(1\leq i\leq m) $，序列 $ a[l_i,r_i] $ 中的所有元素都是唯一的。如果没有必要进行这个操作，答案为 $ 0 $。求进行操作时选择的子段的最小长度。 **输入数据格式：** - 第一行输入一个整数 $ t(1\leq t\leq100) $ 表示数据组数。 - 每组数据： - 第一行输入两个整数 $ n,m(1\leq n,m,\sum n,\sum m\leq2\times10^5) $，分别表示序列长度和给定的数对数。 - 接下来一行输入 $ n $ 个整数表示序列 $ a_1,a_2,\cdots,a_n(1\leq a_i\leq10^9) $。 - 接下来输入 $ m $ 行，每行输入两个整数表示数对 $ l_i,r_i(1\leq l_i\leq r_i\leq n) $。 **输出数据格式：** - 对于每组数据，输出进行操作时选择的子段的最小长度。如果没有必要进行操作，输出 $ 0 $。 **样例解释：** - 第一组数据，可以选择子段 $[1,2]$ 并将序列改成 $[5,6,2,1,3,3,5]$，此时每个数对都满足要求，且没有更优的答案，因此答案为 $ 2 $。 - 第二组数据，没有必要进行操作。 - 第三组数据，可以选择子段 $[1,1]$ 并将序列改成 $[1,7,5,6]$。