Problem

We are given a sequence (a_1, a_2, \ldots, a_n) of length (n) and (m) distinct integers (b_1, b_2, \ldots, b_m). We perform a fierce cut on sequence (a) based on the numbers in (b). Specifical, for each position (i) where (a_i) equals some (b_j), we remove the element at that position, splitting the current sequence/fragment into two fragments (left and right). After performing all possible cuts, we need to count how many fragments remain. A fragment must contain at least one element. Positions at the beginning (index 1) or end (index n) that are cut points do not create fragments out side the sequence.

The problem is from Luogu P8889, and the hard version has larger constraints.

Input Format

• First line: two integers (n) and (m).
• Second line: (n) integers representing sequence (a).
• Third line: (m) integers representing set (b) (distinct).

Output Format

A single integer: the number of fragments after all cuts.

Sample Input 1

6 2
3 4 3 5 2 6
5 4

Sample Output 1: 3

Sample Input 2

6 3
3 4 3 5 2 6
3 5 6

Sample Output 2: 2

Solution

The naive approach would be to scan both arrays for matching values, which is (O(n m)) and too slow. We need optimization.

Key Idea: Sort both sequences. But we must preserve the original order of (a) to reconstruct fragments. So we store (a) as vector of pairs (value, index). We sort (a) by value, and also sort (b). Then use a two-pointer technique to mark cut positions: for each match, set the value of that (a) element to 0 (or a special marker). Since (b) elements are distinct, we handle duplicates in (a). Finally, sort (a) back by index and count fragments.

Steps:

1. Read (n, m).
2. Create vector a of pairs (value, index). Read (a) values with index starting from 0.
3. Read (b) into array.
4. Sort (b) ascending.
5. Sort a by value.
6. Two pointers: i for a, j for b. While both within bounds:
   • If a[i].value == b[j]: set a[i].value = 0, increment i. (Do not increment j because there might be another same value in a).
   • Else if a[i].value < b[j]: increment i.
   • Else (a[i].value > b[j]): increment j.
7. Sort a back by index.
8. Count fragments: iterate through a, when we encounter a non-zero value, start a fragment and skip consecutive non-zero values (they belong to same fragment). Each fragment corresponds to a block of consecutive positions that are not cut.

Time Complexity: (O(n \log n + m \log m)) due to sorting. Space: (O(n+m)).

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<pii> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];
    
    sort(b.begin(), b.end());
    sort(a.begin(), a.end(), [](const pii& p, const pii& q) {
        return p.first < q.first;
    });
    
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i].first == b[j]) {
            a[i].first = 0;
            i++;
        } else if (a[i].first < b[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    sort(a.begin(), a.end(), [](const pii& p, const pii& q) {
        return p.second < q.second;
    });
    
    int ans = 0;
    for (int k = 0; k < n; k++) {
        if (a[k].first != 0) {
            ans++;
            while (k < n && a[k].first != 0) k++;
            k--; // for loop will increment
        }
    }
    cout << ans << '\n';
    
    return 0;
}

Conclusion

This problem is a classic example of using sorting and two-pointer technique to efficiently mark elements for deletion while preserving order for fragment counting.