{"problem":{"name":"[语言月赛202212] 狠狠地切割(Easy Version)","description":{"content":"现给你一个长度为 $n$ 的序列 $a _ 1, \\cdots, a _ n$ 和 $m$ 个互不相同的整数 $b _ 1, \\cdots, b _ m$。你需要按照这 $m$ 个数对序列 $a$ 进行**狠狠地切割**。 具体的，对于一个数字 $i \\in [1, n]$，如果存在一个整数 $j \\in [1, m]$，使得 $a _ i = b _ j$，则将位置 $i$ 称为一个**切割点","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3691"},"statements":[{"statement_type":"Markdown","content":"现给你一个长度为 $n$ 的序列 $a _ 1, \\cdots, a _ n$ 和 $m$ 个互不相同的整数 $b _ 1, \\cdots, b _ m$。你需要按照这 $m$ 个数对序列 $a$ 进行**狠狠地切割**。\n\n具体的，对于一个数字 $i \\in [1, n]$，如果存在一个整数 $j \\in [1, m]$，使得 $a _ i = b _ j$，则将位置 $i$ 称为一个**切割点**。对序列 $a$ 中的每一个切割点，我们在这个位置进行一次**狠狠地切割**。方法是，将该位置的数字去除，然后在这个位置将其左右的**序列/片段**一分两半。\n\n如果对**狠狠地切割**的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。\n\n你需要计算，在进行了所有可能的**狠狠地切割**后，序列被切割为了多少**片段**。\n\n特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做**片段**。同样的，如果 $1$ 或 $n$ 为切割点，其与开头和结尾之间也不存在片段。\n\n如果对**片段**的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。\n\n## Input\n\n第一行为两个整数，依次表示序列 $a$ 的长度 $n$ 和序列 $b$ 的长度 $m$。  \n第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。  \n第三行有 $m$ 个整数，第 $i$ 个整数表示 $b_i$。\n\n## Output\n\n输出一个整数，代表**狠狠地切割**后的**片段**的个数。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n在**狠狠地切割**前，序列 $a$ 如下所示：\n\n$$\\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \\end{matrix}$$\n\n容易知道，第二个位置和第四个位置为切割点，我们使用 `|` 对其进行替换，代表去除工作：\n\n$$\\begin{matrix} 3 & | & 3 & | & 2 & 6 \\end{matrix}$$\n\n我们将片段进行简单的标记：\n\n$$\\begin{matrix} \\overbrace{3} ^ \\text{片段 1} & | & \\overbrace{3} ^ \\text{片段 2} & | & \\overbrace{2 \\quad 6} ^ \\text{片段 3} \\end{matrix}$$\n\n共计 $3$ 个片段。\n\n### 样例 2 解释\n\n以下我们展示去除之后的序列：\n\n$$\\begin{matrix} | & 4 & | & | & 2 & | \\end{matrix}$$\n\n我们将片段进行简单的标记：\n\n$$\\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}$$\n\n共计 $2$ 个片段。\n\n### 数据规模与约定\n\n- 对于 $20\\%$ 的数据，保证 $n, m \\leq 10$。\n- 对于 $70\\%$ 的数据，保证 $n, m \\leq 5 \\times 10 ^ 3$。\n- 对于 $100\\%$ 的数据，保证 $1 \\leq n, m \\leq 5 \\times 10 ^ 5$，$1 \\leq a_i,b_i \\leq 5 \\times 10^{6}$。\n\n### 提示\n本题输入规模较大，建议考虑使用较快的读入读出方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3691","tags":["二分","2022","O2优化","排序","双指针 two-pointer","语言月赛"],"sample_group":[["6 2\n3 4 3 5 2 6\n5 4","3"],["6 3\n3 4 3 5 2 6\n3 5 6","2"]],"created_at":"2026-03-03 11:09:25"}}