#B3691. [语言月赛202212] 狠狠地切割(Easy Version)

    ID: 240 远端评测题 1000ms 512MiB 尝试: 1 已通过: 0 难度: 10 上传者: 标签>二分2022O2优化排序双指针,two-pointer数组语言月赛

[语言月赛202212] 狠狠地切割(Easy Version)

题目背景

本题与 H2 的题意完全一致,区别仅在数据范围

题目描述

现给你一个长度为 nn 的序列 a1,,ana _ 1, \cdots, a _ nmm 个互不相同的整数 b1,,bmb _ 1, \cdots, b _ m。你需要按照这 mm 个数对序列 aa 进行狠狠地切割

具体的,对于一个数字 i[1,n]i \in [1, n],如果存在一个整数 j[1,m]j \in [1, m],使得 ai=bja _ i = b _ j,则将位置 ii 称为一个切割点。对序列 aa 中的每一个切割点,我们在这个位置进行一次狠狠地切割。方法是,将该位置的数字去除,然后在这个位置将其左右的序列/片段一分两半。

如果对狠狠地切割的定义有疑问,可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算,在进行了所有可能的狠狠地切割后,序列被切割为了多少片段

特别的,如果在切割后,某一段内没有数组,那这一段不可被叫做片段。同样的,如果 11nn 为切割点,其与开头和结尾之间也不存在片段。

如果对片段的概念有疑问,可以参照「样例 #2」及「样例解释 #2」进行理解。

输入格式

第一行为两个整数,依次表示序列 aa 的长度 nn 和序列 bb 的长度 mm
第二行有 nn 个整数,第 ii 个整数表示 aia_i
第三行有 mm 个整数,第 ii 个整数表示 bib_i

输出格式

输出一个整数,代表狠狠地切割后的片段的个数。

6 2
3 4 3 5 2 6
5 4
3
6 3
3 4 3 5 2 6
3 5 6
2

提示

样例 1 解释

狠狠地切割前,序列 aa 如下所示:

343526\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}

容易知道,第二个位置和第四个位置为切割点,我们使用 | 对其进行替换,代表去除工作:

3326\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}

我们将片段进行简单的标记:

$$\begin{matrix} \overbrace{3} ^ \text{片段 1} & | & \overbrace{3} ^ \text{片段 2} & | & \overbrace{2 \quad 6} ^ \text{片段 3} \end{matrix} $$

共计 33 个片段。

样例 2 解释

以下我们展示去除之后的序列:

42\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}

我们将片段进行简单的标记:

$$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} | & \overbrace{4} ^ \text{片段 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} & | & \overbrace{2} ^ \text{片段 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段}\end{matrix} $$

共计 22 个片段。

数据规模与约定

  • 对于 20%20\% 的数据,保证 n,m10n, m \leq 10
  • 对于 70%70\% 的数据,保证 n,m5×103n, m \leq 5 \times 10 ^ 3
  • 对于 100%100\% 的数据,保证 1n,m5×1051 \leq n, m \leq 5 \times 10 ^ 51ai,bi5×1061 \leq a_i,b_i \leq 5 \times 10^{6}

提示

本题输入规模较大,建议考虑使用较快的读入读出方式。