近段时间出现可以用multiset解决的题目
AtCoder Beginner Contest 308 G Minimum Xor Pair Query
题意：有一个数组进行 \(3\) 种操作:
- 加一个数
- 删一个数
- 打印数组 \(\min _{ 1 \leq i < j \leq n} {a_i \bigoplus a_j}\)
结论：拍序后的数组，其最小异或对在相邻两数中产生
那么我们就需要维护一个数的多重集合，一个异或值的多重集合
在每次插入时 例如 \(x, y\) -> \(x , y, z\) 在异或值的多重集合中删除 \(x \bigoplus z\) ，插入入 \(x \bigoplus y\) ， \(y \bigoplus z\)
同理删除时\(x, y, z\) -> \(x, z\) 在异或值的多重集合删除 \(x \bigoplus y\) ， \(y \bigoplus z\) 插入 \(x \bigoplus z\)
打印就输出异或值的多重集合的最小值即可
// LUOGU_RID: 117557481
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const ll up = 1 << 30;
multiset<ll> s, res;
int q;
void add(ll x)
{
s.insert(x);
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.erase(res.find((*it1) ^ (*it2)));
if(*it1 != -1)
res.insert(x ^ (*it1));
if(*it2 != up)
res.insert(x ^ (*it2));
//cout<<x<<'\n';
}
void del(ll x)
{
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.insert((*it1) ^ (*it2));
if(*it1 != -1)
res.erase(res.find((*it1) ^ x));
if(*it2 != up)
res.erase(res.find(x ^ (*it2)));
s.erase(s.find(x));
}
void solve()
{
cin>>q;
s.insert(-1); s.insert(up);
for(int i = 1; i <= q; i++)
{
int opt; cin>>opt;
if(opt == 3)
{
cout<<*res.begin()<<'\n';
}
else
{
ll x; cin>>x;
if(opt == 1)
add(x);
else if(opt == 2)
del(x);
}
}
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
//cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
G - The Great Equalizer
找了个规律，\(res = \text{排序后数组中最大的差} + \text{数组中最大的元素}\)
怎么处理这个问题呢，用multiset处理一下，最近cf，atc都出过两次可以用同样方法解决的题目了，先去吃个饭，待补
update：每次操作使得排序后数组中相邻两数的差减少 \(1\) ，数组中的最大值又会增加 \(1\) ，所以 \(res = \text{排序后数组中最大的差} + \text{数组中最大的元素}\)
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const ll up = 1ll << 60;
ll n, q, a[N];
multiset<ll> s, res;
void add(ll x)
{
s.insert(x);
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.erase(res.find((*it2) - (*it1)));
if(*it1 != -1)
res.insert(x - (*it1));
if(*it2 != up)
res.insert((*it2) - x);
//cout<<x<<'\n';
}
void del(ll x)
{
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.insert((*it2) - (*it1));
if(*it1 != -1)
res.erase(res.find(x - (*it1)));
if(*it2 != up)
res.erase(res.find((*it2) - x));
s.erase(s.find(x));
}
void solve()
{
cin>>n;
res.clear(); s.clear();
s.insert(-1); s.insert(up);
for(int i = 1; i <= n; i++)
{
cin>>a[i];
add(a[i]);
}
cin>>q;
for(int i = 1; i <= q; i++)
{
ll p, x; cin>>p>>x;
del(a[p]); a[p] = x; add(a[p]);
if(n == 1)
{
cout<<a[n]<<" ";
continue;
}
cout<<*(--(--s.end())) + *(--res.end())<<" ";
}
cout<<'\n';
return;
}