提供两种思路:
一:使用 set,因为 set 去重,所以对每个元素,将它添加一个索引值变成一个二元组 pair,就可以当可重复的 set 来使用了。
二:使用 multiset。注意 erase(v) 本身是会删掉所有 v 的,要用 erase(迭代器) 才会删掉单个值。
具体细节参见代码。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
set<pair<ll, ll>> s;
signed main()
{
cin.tie(0)->ios::sync_with_stdio(false);
cin >> n;
for (ll i = 1, op, x; i <= n; ++i)
{
cin >> op >> x;
if (op == 1)
{
s.insert({x, i});
}
else if (op == 2)
{
auto pr = s.lower_bound({x, 0});
if (pr != s.end() && pr->first == x)
{
s.erase(pr);
}
}
else if (op == 3)
{
auto pr = s.lower_bound({x, 0});
if (pr != s.begin())
{
--pr;
s.erase(pr);
}
}
else if (op == 4)
{
auto pr = s.lower_bound({x, 1e9});
if (pr != s.end())
{
s.erase(pr);
}
}
else if (op == 5)
{
auto pr = s.lower_bound({x, 0});
cout << (pr != s.end() && pr->first == x ? "yes\n" : "no\n");
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
multiset<ll> s;
ll n;
signed main()
{
// cin.tie(0)->ios::sync_with_stdio(false);
cin >> n;
for (ll i = 1, op, x; i <= n; ++i)
{
cin >> op >> x;
if (op == 1)
{
s.insert(x);
}
else if (op == 2)
{
if (s.find(x) != s.end())
{
// s.erase(x);错误:删除所有x
s.erase(s.find(x));
}
}
else if (op == 3)
{
auto pr = s.lower_bound(x);
if (pr != s.begin())
{
--pr;
if (*pr < x)
{
s.erase(pr);
}
}
}
else if (op == 4)
{
auto pr = s.upper_bound(x);
if (pr != s.end())
{
s.erase(pr);
}
}
else if (op == 5)
{
cout << (s.find(x) == s.end() ? "no\n" : "yes\n");
}
}
return 0;
}