#D. 藏品分区

    传统题 1000ms 256MiB

藏品分区

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

【题目描述】

小博最近迷上了整理他的收藏品。这些收藏品排列成一个长度为n的队列,依次标号为,表示每件藏品的编号。同时,小博有一份特别的列表,记录了一些他认为需要特别保管的藏品编号。

小博决定对他的收藏队列进行重新分区,规则如下:

• 每当小博发现某件藏品的编号在特别列表中时,他会移除这件藏品,并将它前后的两部分收藏分成独立的分区。

• 经过所有操作后,剩余的每一段连续收藏(即不包含移除藏品的部分)就成为一个分区。

现在小博想知道,经过所有特别藏品移除和分区操作后,他的收藏被分为了多少个独立分区?他需要你的帮助来计算这个结果!

【输入格式】

第一行为两个整数,依次表示序列 a 的长度 n 和序列 b 的长度 m。

第二行有 n 个整数,第 i 个整数表示 。

第三行有 m 个整数,第 i个整数表示 。

【输出格式】

输出一个整数,代表分区的数量。

【样例1输入】

6 2
3 4 3 5 2 6
5 4

【样例1输出】

3

【样例1解释】

在分区前,藏品序列a如下所示:3 4 3 5 2 6

根据题目要求,第2个位置和第4个位置作为分区的界限,我们可以使用 | 作为给藏品分区的界限,那么是:3 | 3 | 2 6 共三个分区。

【样例2输入】

6 3
3 4 3 5 2 6
3 5 6

【样例2输出】

2

【数据规模与规定】

20%的数据:n,m≤10。

70%的数据:n,m≤5000,1≤ai,bi5106a_i,b_i\leq5*10^6

100%的数据:1≤n,m≤500000,1≤ai,bi109a_i,b_i\leq10^9

2024.12.1图灵编程月赛城阳小学组同步赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-12-1 18:10
结束于
2024-12-1 21:10
持续时间
3 小时
主持人
参赛人数
9