#19281. 毕昇的字架

毕昇的字架

你好!我是你的OI金牌教练。

刚才在演示样例逻辑时,为了展示思维过程显得有些啰嗦。 这里为你整理了修正后、精简且完全正确的版本。这道题结合了北宋活字印刷术的历史背景,考察 GESP 6级 核心算法——双指针/滑动窗口


第一部分:背景知识讲解

1. 活字印刷术 (Movable Type Printing)

北宋庆历年间,毕昇发明了胶泥活字印刷术。相比于之前的雕版印刷,活字印刷的特点是“字是活的”,可以随意拼凑组合。

2. 排版效率问题

工匠需要在一个巨大的字架上寻找所需的汉字。如果所需的字分布在字架的一小段连续区域内,工匠就可以站定不动,快速取完所有字;反之,如果字分布太散,工匠就要来回奔波。 因此,如何在长序列中找到包含所有目标元素的最小区间,就成了一个经典的算法问题。


第二部分:题目内容

题目名称:毕昇的字架 (Bi Sheng's Type Rack)

题目描述

毕昇的工坊里有一个长条形的字架,上面按顺序摆放了 NN 个活字。为了方便记录,我们用数字 120001 \sim 2000 来代表不同的汉字。字架上的活字编号依次为 A1,A2,,ANA_1, A_2, \dots, A_N

现在,工匠需要排印一个包含 MM 种不同汉字的标题。这 MM 种汉字的编号分别是 T1,T2,,TMT_1, T_2, \dots, T_M

为了节省体力,工匠希望在字架上找到一个连续的区间 [L,R][L, R],使得这个区间内至少包含MM 种所需的汉字(区间内可以包含其他无关的字,也可以包含多余的所需字)。

请你编写程序,计算出满足条件的最小区间长度(即 RL+1R - L + 1 的最小值)。如果字架上找不到包含所有所需汉字的区间,请输出 Impossible

输入格式

第一行包含两个正整数 N,MN, M

  • NN 表示字架上活字的总数。
  • MM 表示需要排印的汉字种类的数量。

第二行包含 NN 个正整数 A1,A2,,ANA_1, A_2, \dots, A_N,表示字架上依次摆放的汉字编号。

第三行包含 MM 个正整数 T1,T2,,TMT_1, T_2, \dots, T_M,表示需要排印的那 MM 种汉字的编号(保证互不相同)。

输出格式

输出一行。如果有解,输出最小连续区间的长度;无解则输出 Impossible

输入输出样例 #1

输入:

10 3
1 2 3 5 4 2 1 5 3 6
1 3 5

输出:

3

样例 #1 解释: 我们需要找到包含 {1, 3, 5} 的最小区间。

  • 整个字架序列为:1 2 3 5 4 2 1 5 3 6
  • 区间 [1,4][1, 4] 内容为 1 2 3 5,包含所有目标,长度为 4。
  • 区间 [7,9][7, 9] 内容为 1 5 3,包含所有目标,长度为 3
  • 长度 3 是最小的,故输出 3。

输入输出样例 #2

输入:

5 3
1 2 1 2 1
1 2 3

输出:

Impossible

样例 #2 解释: 字架上只有 1 和 2,无论怎么选区间,都找不到 3。

数据范围

对于 100%100\% 的数据:

  • 1N1061 \le N \le 10^6
  • 1M20001 \le M \le 2000
  • 汉字编号范围 120001 \sim 2000