本文章由 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;
}
鲁ICP备2025150228号