P8889 [入门赛 #7] 狠狠地切割 (Hard Version)

#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 500050;
long long int a[maxn];
long long int n, x, m, sum;
long long int b[maxn];
bool check(long long int k)
{ // ai是否在b中
    long long int l = 1, r = m, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (k < b[mid])
        {
            r = mid-1;
        }
        else if (k > b[mid])
        {
            l = mid + 1;
        }
        else
            return 1;
    }
    return 0;
}
 int main()
{
    cin >> n >> m;
    for (long long int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    for (long long int i = 1; i <= m; i++)
    {
        scanf("%lld", &b[i]);
    }
    long long int ans = 0;
    sort(b + 1, b + m + 1);
    //二分b前要先对b排序
    for (long long int i = 1; i <= n; i++)
    {
        if (check(a[i]))
        { // 能否被切割
            a[i] = 0;
        }
    }
    long long int flag = 0;
    for (long long int i = 1; i <= n; i++)
    {
        if (a[i] != 0 && flag == 0)
        {
            flag = 1;
            ans++;
        }
        if (a[i] == 0 && flag == 1)
        {
            flag = 0;
        }
    }
    cout << ans;
}