近段时间出现可以用multiset解决的题目

AtCoder Beginner Contest 308 G Minimum Xor Pair Query

题意：有一个数组进行 \(3\) 种操作:

1. 加一个数
2. 删一个数
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;
}