南师大算法竞赛域
Powered by Vijos
/ 南师大算法竞赛域 / 比赛 / 2023秋 苏州青少年科技馆（吴江计算机协会）CSP-J/S模拟赛（1） /

4. Different sequence

4. Different sequence

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Different sequence

时间限制：1s

空间限制：64MB

题目描述

定义【 全异序列 】：即一段连续的序列满足序列中的数值 互不相同。

请寻找合适的算法以找出序列区间 [L, R] 之间最长全异序列的长度。

数据格式

输入

第一行两个整数 N，M。N 表示连续 N 个数，编号为 0 到 N−1，M 表示询问的次数；

第二行 N 个整数，第 i 个数表示该序列第 i 个数的值；

接下来 M 行每行两个整数 L，R，表示询问的区间。

输出

输出 M 行，每行一个整数，对应询问区间内的最长全异序列的长度。

样例1

输入：

9 2
172 175 174 171 172 173 176 172 174
0 8
2 6
Copy

输出：

6
5
Copy

样例2

输入：

50 50
725 484 509 297 277 201 695 142 299 565 104 903 564 647 253 533 794 935 831 911 49 305 702 626 627 292 71 733 727 260 121 98 774 908 436 354 446 440 611 504 146 97 956 433 25 258 390 698 382 332 
34 37
1 22
19 47
38 47
14 14
22 46
45 48
34 48
24 30
38 39
31 39
6 43
33 35
8 44
8 33
5 19
6 10
38 44
43 45
16 34
6 39
22 35
43 44
45 49
32 37
2 8
18 41
7 47
18 31
45 46
39 45
26 40
47 48
26 33
17 40
35 46
37 48
13 39
40 48
14 42
1 12
34 39
11 35
33 35
8 27
26 41
4 46
25 43
32 48
27 40
Copy

输出：

4
22
29
10
1
25
4
15
7
2
9
38
3
37
26
15
5
7
3
19
34
14
2
5
6
7
24
41
14
2
7
15
2
8
24
12
12
27
9
29
12
6
25
3
20
16
43
19
17
14
Copy

样例解释

在第一个样例中：

  1. 区间 [0,8][0,8] 中的最长全异序列为 [172,175,174,171,173,176][172,175,174,171,173,176] ;
  2. 区间 [2,6][2,6] 中的最长全异序列为 [174,171,172,173,176][174,171,172,173,176] 。

数据范围及约定

测试点编号 约定 测试点分值
1~4 1≤N,M≤200,∣ai∣≤2001 ≤ N, M ≤ 200, \vert{a_i}\vert≤200 每个测试点 10 分
5~10 1≤N,M≤2×105,∣ai∣≤1061 ≤ N, M ≤ 2×10^5,\vert{a_i}\vert\le10^6 每个测试点 10 分

规定：对所有测试用例，满足 0≤L≤R≤N−10 ≤ L ≤ R ≤ N − 1 。

2023秋 苏州青少年科技馆（吴江计算机协会）CSP-J/S模拟赛（1）

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-10-07 18:30
结束于
2023-10-07 21:00
持续时间
2.5 小时
主持人
参赛人数
46
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1