90分求助!!!
查看原帖
90分求助!!!
844496
J_Kobe楼主2024/7/8 11:14
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
int n, m, b[N], ans;
bool f[N];
struct node{
	int a, id, f;
} a[N];
bool cmp1(node a, node b)
{
	return a.a < b.a;
}
bool cmp2(node a, node b)
{
	return a.id < b.id;
}

signed main()
{
	ios::sync_with_stdio();
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].a;
		a[i].id = i;
	}
	sort(a + 1, a + 1 + n, cmp1);
//	for (int i = 1; i <= n; i++)
//	{
//		cout << a[i].a << ' ';
//	}
//	cout << endl;
	for (int i = 1; i <= m; i++)
	{
		cin >> b[i];
		int l = 1, r = n, id = -1;
		while (l < r)
		{
			int mid = (l + r) / 2;
//			cout << mid << ' ' << a[mid].a << ' ';
			if (a[mid].a < b[i])
			{
				l = mid + 1;
			}
			else if (a[mid].a > b[i])
			{
				r = mid;
			}
			else
			{
				id = mid;
				break;
			}
//			cout << l << ' ' << r << endl;
		}
//		cout << r << endl;
		if (id == -1)
		{
			continue;
		}
		for (int j = id; j >= 1 && a[j].a == b[i]; j--)
		{
			a[j].f = -1;
		}
		for (int j = id; j <= n && a[j].a == b[i]; j++)
		{
			a[j].f = -1;
		}
	}
//	cout << endl;
	sort(a + 1, a + 1 + n, cmp2);
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
//		cout << a[i].f << ' ';
		if (a[i].f == 0)
		{
			sum++;
		}
		else
		{
			if (sum)
			{
				ans++;
			}
			sum = 0;
		}
	}
	if (sum)
	{
		ans++;
	}
	cout << ans;
	return 0;
}

/*
6 4
3 4 3 5 2 6
2 3 4 5
*/
2024/7/8 11:14
加载中...