CodeForces - 1354D Multiset(树状数组倍增找第k大)

题目链接

题目大意

??模拟一下multiset,一共有两个操作:
??1.插入一个数
??2.删除第k小的数

解题思路

??用权值树状数组来维护,主要是新学了树状数组倍增的方法,可以比二分少一个log来查找第k小的数,需要maxn是2的幂。
??比如要查找第k小的数,我们倒着枚举二进制位,如果区间\([0, 2^x]\)的数的数量比k要小,那么说明第k小的数肯定是比\(2^x\)要大的,那么根据二进制的性质,这个数肯定是介于\([2^x, 2^{x+1}]\)之间的,那么我们就用一个变量res加上\(2^x\),然后k减去其中的数量。再继续枚举更低位,判断区间\([res, res+2^y]\)的数是否比k大,来继续更新res和k的值,这样可以再复杂度为log(n)的情况下找出第k小数。

const int maxn = 1<<20;
const int maxm = 2e5+10;
int n, q, c[maxn+1];
void add(int x, int y) {
    while(x<maxn) {
        c[x] += y;
        x += x&-x;
    }
}
int get_k(int x) {
    int res = 0;
    for (int i = maxn/2; i>=1; i>>=1) 
        if (c[res+i]<x) {
            res += i;
            x -= c[res];
        }
    return res+1;
}
int main(void) { 
    IOS;
    cin >> n >> q;
    for (int i = 1; i<=n; ++i) {
        int num; cin >> num;
        add(num, 1);
    }
    while(q--) {
        int num; cin >> num;
        if (num>0) add(num, 1);
        else {
            num = -num;
            int x = get_k(num);
            add(x, -1);
        }
    }
    int ans = 0;
    for (int i = 1; i<maxn; ++i)
        if (c[i]) {
            ans = i;
            break;
        }
    cout << ans << endl;
    return 0;   
}

CodeForces - 1354D Multiset(树状数组倍增找第k大)

上一篇:python数据类型之“字符串”


下一篇:C++基础数据类型