藏品分区
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题目描述】
小博最近迷上了整理他的收藏品。这些收藏品排列成一个长度为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≤。
100%的数据:1≤n,m≤500000,1≤。