因为数据很小,所以用线段树加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;
}