Link

ABC330 E Mex and Update

Question

给一个数组 \(a\)，有 \(Q\) 次修改

每次把 \(a_i\) 改成 \(x\)

问每次修改后，不在 \(a\) 数组中的最小非负数时多少

Solution

记录每个 \(a_i\) 出现的次数 \(num\)

每个修改操作可以看成时先删除，后添加

用 set 维护为 \(num_x=0\) 的 \(x\)

如果一个数的个数被删到 \(0\) 了，就添加到 \(set\) 里面

如果一个原来 \(num\) 为 \(0\) 的数需要添加了，就从 \(set\) 里面删去

每次取 \(set\) 的 \(begin()\) ，就是答案

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
map<int,int> mp;
int a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    freopen("E.in","r",stdin);
    int N=read(),Q=read();
    for(int i=1;i<=N;i++){
        a[i]=read();
        map<int,int>::iterator it=mp.find(a[i]);
        if(it!=mp.end())
            it->second++;
        else 
            mp[a[i]]=1;
    }
    for(int i=1;i<=Q;i++){
        int pos=read(),val=read();
        
        if(!--mp[a[pos]])
            mp.erase(a[pos]);
        
        a[pos]=val;
        map<int,int>::iterator it=mp.find(val);
        if(it!=mp.end())
            it->second++;
        else 
            mp[a[pos]]=1;
        
    }
}