【題解】Codeforces 1354D. Multiset

#include <iostream>
using namespace std;
 
int n, q, a, cnt, bit[1000005];
 
void update(int x, int y){
    cnt += y;
    while (x <= n){
        bit[x] += y;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
int f(int tar){
    int ans = 0;
    for (int i = 19; i >= 0; i--){
        if (ans+(1<<i) <= n && bit[ans+(1<<i)] < tar){
            tar -= bit[ans+(1<<i)];
            ans += (1<<i);
        }
    }
    return ans+1;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        cin >> a;
        update(a, 1);
    }
    for (int i = 0; i < q; i++){
        cin >> a;
        if (a > 0) update(a, 1);
        else update(f(-a), -1);
    }
    if (cnt) cout << f(1);
    else cout << 0;
}