本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-02 16:12:05

方法一：set

不解释，题解好多。

方法二：BIT

a桶数组。c是否出现。a[i]==0时候，放在c权值中，否则删除。

怎样查询？ 二分查找前缀和为0的位置。

\/*
https:\/\/atcoder.jp\/contests\/abc330\/submissions\/48086953
written by : zjs123
QQ : 755328053
Wechat : zoujinshu18
CZOJ : zjs123
luogu : Running_For_Dream
atcoder : zajasi10
codeforces : vegetable_zajasi
*\/
#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+9; 
int n,t;
int a[N],c[200020],k[200020];
 
int x,y;
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    if(x>n)return;
    int y=x;
    if(k[x]==0){
        x++;
        while(x<=n){
            c[x]++;
            x+=lowbit(x);
        }
    }
    k[y]++;
}
void move(int x){
    if(x>n)return;
    int y=x;
    if(k[x]==1){
        x++;
        while(x<=n){
            c[x]--;
            x+=lowbit(x);
        }
    }
    k[y]--;
}
int find(int x){
    int re=0;
    while(x){
        re+=c[x];
        x-=lowbit(x);
    }
    return re;
}
int search(){
    if(k[0]==0)return 0;
    int l=0,r=n;
    while(l<=r){
        int mid=(l+r)\/2;
        if(find(mid+1)==mid+1)l=mid+1;
        else r=mid-1;
    }
    return l;
}
main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(a[i]);
    }
    while(t--){
        cin>>x>>y;
        move(a[x]);
        a[x]=y;
        add(y);
        cout<<search()<<"\n";
    }
    return 0;
}

BIT直接二分，少一个log复杂度

\/*
https:\/\/atcoder.jp\/contests\/abc330\/submissions\/48086953
written by : zjs123
QQ : 755328053
Wechat : zoujinshu18
CZOJ : zjs123
luogu : Running_For_Dream
atcoder : zajasi10
codeforces : vegetable_zajasi
*\/
#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+9;
int n,t;
int a[N],c[200020],k[200020];
\/\/a桶数组。c是否出现。a[i]==0时候，放在c权值中，否则删除。
\/\/怎样查询？ 二分查找前缀和为0的位置。
int x,y;
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    if(x>n)return;
    int y=x;
    if(k[x]==0){
        x++;
        while(x<=n){
            c[x]++;
            x+=lowbit(x);
        }
    }
    k[y]++;
}
void move(int x){
    if(x>n)return;
    int y=x;
    if(k[x]==1){
        x++;
        while(x<=n){
            c[x]--;
            x+=lowbit(x);
        }
    }
    k[y]--;
}
int find(int x){
    int re=0;
    while(x){
        re+=c[x];
        x-=lowbit(x);
    }
    return re;
}
int search(){
    if(k[0]==0)return 0;
    
    int _log=log2(n);
    int res = 0, sum = 0;
    for (int j = _log; j >= 0; j--) {
			if (res+(1<<j) <= n && sum + c[res+(1<<j)] == res+(1<<j))
                res += 1 << j,sum+=c[res];
        }

        return res;
}
main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(a[i]);
    }
    while(t--){
        cin>>x>>y;
        move(a[x]);
        a[x]=y;
        add(y);
        cout<<search()<<"\n";
    }
    return 0;
}

方法三线段树写法

sz出现的次数。mex如果有这个数值就是1e9,没有这个数值就是最小没有出现过的数，也就是左端点。用线段树树叶维护没有出现过得左端点。其他节点维护最小值。查询根节点最小值即可。

单点修改sz，sz到了0，就修改mex。区间查询mex的最小值。

\/\/cxm代码 .超过n的数没有用，不管他。
#include <bits\/stdc++.h>
using namespace std;
int n, q, a[200010], cnt, rt;
struct node {
	int sz, mex, lson, rson;
	
} t[200010 * 160];
#define mid (l + r >> 1)
void add(int &now, int x, int y, int l = 0, int r = 1e9) {
	if (now == 0) now = ++cnt, t[now].mex = l;
	if (x < l || x > r) return;
	t[now].sz += y;
	if (l == r) {
		if (t[now].sz) t[now].mex = 1e9;
		else t[now].mex = l;
		return;
	}
	add(t[now].lson, x, y, l, mid);
	add(t[now].rson, x, y, mid + 1, r);
	t[now].mex = min(t[t[now].lson].mex, t[t[now].rson].mex);\/\/ 
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i], add(rt, a[i], 1);
	while (q--) {
		int x, y;
		cin >> x >> y;
		add(rt, a[x], -1);
		a[x] = y, add(rt, y, 1); \/\/单点修改两次，a[x]消失，y出现。 
		cout << t[rt].mex << endl;\/\/单点查询跟结点。 
	}
	return 0;
}