title: stl的妙用
categories:
- ICPC
tags:
- null
abbrlink: 294436d6
date: 2023-04-03 00:00:00

stl的妙用

关于mutiset的应用的几个题

G - Minimum Xor Pair Query

题意：你可以进行以下操作

加入一个数
删除一个数
输出任意两个数异或最小值

思路：首先我们要知道一个性质(重要!)：两个数差值越小，异或值也越小。

那么我们要求异或最小值，那么答案一定在排序后相邻两个数中产生。

为了便于写，防止在set里面找不到的情况出现，我们手动插入下界和上界。

考虑我们的操作：

对于加入一个数，我们的答案有什么影响呢？

假设我们插入的值是x。

假设我们的情况是：l x r

首先如果l和r都存在，那么显然此时l和r的异或值不可能成为答案，我们把它删去

然后在答案里面加入x^l和 x^r(前提是l，r存在)

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));
}

下面是AC代码：

// AC one more times
// nndbk
#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;
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((*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));
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin>>q;
    s.insert(-1),s.insert(up);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x;
            cin>>x;
            add(x);
        }
        else if(op==2)
        {
            int x;
            cin>>x;
            del(x);
        }
        else
        {
            cout<<*res.begin()<<"\n";
        }
    }
 
 
    return 0;
}

G. The Great Equalizer

题意：

一次运行包含以下操作:

对当前数组排序(不降序),然后删除重复的元素
如果当前数组大小是1，那么停止运行，输出运行结果
对于数组元素加上一个等差数列{n,n−1,n−2,…,1}其中n是当前数组长度
返回第一步

给你q个询问，每次给你i x,表示把a[i]赋值为x。然后运行上述求每次的最终运行结果

通过找规律，我们可以发现，最后的答案是数组最大的元素值+排序后数组中两个数差的最大值。

因为，每次操作，排序后的数组，相邻两个数的差值-1，数组中最大值+1，那么答案就是数组最大的元素值+排序后数组中两个数差的最大值。和上一题类似，不过改成了维护两个数差的最大值。

注意：其实改一个数可以想象成把原本的数删了加入一个新的数。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
 
int t,n,q,a[N];
multiset<ll>s,res;
const ll up = 1ll<<60;
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));
}
 
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>t;
    while(t--)
    {
        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;
        while(q--)
        {
            int i,x;
            cin>>i>>x;
            del(a[i]);
            a[i] = x;
            add(a[i]);
            if(n==1){
                cout<<a[n]<<"\n";
                continue;
            }
            cout<<*(--(--s.end()))+*(--res.end())<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

维护每个窗口的最早空闲时间，然后更新就行。

#include <bits/stdc++.h>

#define fi first
#define se second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<LL> a(n), v(m), belong(n), cnt(m), t(m);
    for(auto &x : v) cin >> x;
    for(auto &x : a) cin >> x;
    sort(all(a));
    set<PII> st; // cnt, id
    set<PLI> done; // time, id
    for(int i = 0; i < m; i ++) 
        st.insert({0, i});
    for(int i = 0; i < n; i ++) {
        while(done.size() && done.begin()->fi <= a[i]) {
            int gid = belong[done.begin()->se];
            done.erase(done.begin());
            st.erase(st.find({cnt[gid], gid}));
            cnt[gid] --;
            st.insert({cnt[gid], gid});
        }
        auto [nn, gid] = *st.begin();
//        cout << nn << ' ' << gid << '\n';
        st.erase(st.begin());
        cnt[gid] ++;
        st.insert({cnt[gid], gid});
        done.insert({max(a[i], t[gid])+v[gid], i});
        belong[i] = gid;
//        cout << t[gid] << '\n';
        
        t[gid] = max(t[gid], a[i])+v[gid];
    }
    cout << (done.rbegin()->fi) << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    
    int Tcase = 1;
//    cin >> Tcase;
    while(Tcase --) 
        solve();
    
    return 0;
}
/*
3 1
100
1 10 301
*/