CF1354D

FiraCode · 2022-11-28 19:27:20 · 题解

题解思路：

这个题有两个操作，先看第二个，就是加数操作。

那么我们就建一棵值域树状数组，然后就直接在 x 的位置加一就可以了。

那么删除的话就可以二分，就是二分第一个满足值 \le mid 的个数是否 = \left | x \right | 就可以了。

这个的时间复杂度是 O(n \log^2 n) 的时间复杂度，需要卡卡常数才可以过。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int &read(int &r){//快读
    r=0;bool w=0;char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
    return r=w?-r:r;
}
int n, q;
template<class T>//线段树模板
struct BIT {
    int c[N];
    void modify(int x, int d) {
        if (x <= 0) return;
        for (; x <= n; x += (x & -x))
            c[x] += d;
    }
    T query(int x) {
        T res = 0;
        for (; x; x -= (x & -x))
            res += c[x];
        return res;
    }
};
BIT<int> c;
int main() {
    read(n), read(q);
    for (int i = 1; i <= n; ++i) {
        int a = read(a);
        c.modify(a, 1);//读入这个序列
    }
    for (int i = 1; i <= q; ++i) {
        int x = read(x);
        if (x > 0) c.modify(x, 1);//把这个x位置+1
        else {
            x = -x;//把x变成|x|
            x = (x < 0 ? -x : x);
            int l = 1, r = n, res = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (c.query(mid) >= x) {//若当前的值<=mid的数的个数是>=x，那么就可以更新答案了。
                    res = mid;
                    r = mid - 1;
                }else l = mid + 1;
            }
            c.modify(res, -1);//把这个减去
        }
    }
    int l = 1, r = n, res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (c.query(mid) >= 1) {//就是求最小的那一个。
            res = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    printf("%d\n", res);
    return 0;
}