P8889 [Beginner Contest #7] Cut It Hard (Hard Version)

**This problem has exactly the same statement as H1. The only difference is the constraints. In the Language Monthly Contest there is no H2 problem. This problem is only used to increase the distinction in the public contest, and it does not strictly follow the contest syllabus. Please solve it as you see fit.**

You are given a sequence $a _ 1, \cdots, a _ n$ of length $n$, and $m$ pairwise distinct integers $b _ 1, \cdots, b _ m$. You need to perform a **hard cut** on the sequence $a$ according to these $m$ numbers. Specifically, for a number $i \in [1, n]$, if there exists an integer $j \in [1, m]$ such that $a _ i = b _ j$, then position $i$ is called a **cut point**. For every cut point in the sequence $a$, we perform one **hard cut** at this position. The method is: remove the number at this position, and then split the **sequence/segment** on its left and right into two parts at this position. If you are unsure about the definition of **hard cut**, you can refer to “Sample #1” and “Sample Explanation #1”. You need to calculate: after performing all possible **hard cuts**, into how many **segments** the sequence is cut. In particular, if after cutting, some part contains no numbers, then this part cannot be called a **segment**. Similarly, if $1$ or $n$ is a cut point, then there is also no segment between it and the beginning or the end. If you are unsure about the concept of **segments**, you can refer to “Sample #2” and “Sample Explanation #2”.

The first line contains two integers, representing the length $n$ of sequence $a$ and the length $m$ of sequence $b$, respectively. The second line contains $n$ integers, where the $i$-th integer is $a_i$. The third line contains $m$ integers, where the $i$-th integer is $b_i$.

Output one integer, representing the number of **segments** after **hard cutting**.

### Sample 1 Explanation Before the **hard cut**, the sequence $a$ is as follows: $$\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}$$ It is easy to see that the second position and the fourth position are cut points. We use `|` to replace them, representing the removal: $$\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}$$ We mark the segments briefly: $$\begin{matrix} \overbrace{3} ^ \text{Segment 1} & | & \overbrace{3} ^ \text{Segment 2} & | & \overbrace{2 \quad 6} ^ \text{Segment 3} \end{matrix}$$ There are $3$ segments in total. ### Sample 2 Explanation Below we show the sequence after removal: $$\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}$$ We mark the segments briefly: $$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment} | & \overbrace{4} ^ \text{Segment 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment} & | & \overbrace{2} ^ \text{Segment 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment}\end{matrix}$$ There are $2$ segments in total. ### Constraints - For $30\%$ of the testdata, it is guaranteed that no element in sequence $a$ appears in $b$. Formally, $\forall i \in [1, n], \forall j \in [1, m], a _ i \neq b _ j$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 5 \times 10 ^ 5$, $- 10 ^ {18} \leq a _ i, b_i \leq 10 ^ {18}$, and the elements in sequence $b$ are pairwise distinct. ### Hint The input size of this problem is large, so it is recommended to use faster input/output methods. Translated by ChatGPT 5