ABC330_E的BIT和线段树解法

· · 个人记录

方法一：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;
}