一个蒟蒻的想法
查看原帖
一个蒟蒻的想法
573963
wbh20090611楼主2024/8/10 15:43

因为数据很小,所以用线段树加map就过了。。。

#include <bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
using namespace std;
const int N = 250005;
int n, a[N], m, ans, minn[N << 2], k;
map <int,int> f;
void build(int root, int l, int r)
{
	if (l == r)
	{
		minn[root] = a[l];
		return;
	}
	build(root << 1, l, mid);
	build((root << 1) + 1, mid + 1, r);
	minn[root] = min(minn[root << 1], minn[(root << 1) + 1]);
	return;
}
int query(int root, int l, int r, int x, int y)
{
	if (l >= x && r <= y)
		return minn[root];
	int an = LONG_LONG_MAX;
	if (mid < y)
		an = min(an, query((root << 1) + 1, mid + 1, r, x, y));
	if (mid >= x)
		an = min(an, query(root << 1, l, mid, x, y));
	return an;
}
signed main()
{
	cin >> n;
	ans = n;
	for (int i = 1; i <= n; i++)
		scanf("%lld%lld", &m, a + i);
	build(1, 1, n);
	for (int i = 1; i <= n; i++)
	{
		if (f.count(a[i]))
		{
			k = f[a[i]];
			if (query(1, 1, n, k, i) >= a[i])
				ans--;
		}
		f[a[i]] = i;
	}
	cout << ans;
	return 0;
}
2024/8/10 15:43
加载中...