Multiset -- CF 1354D

Difficulty: 1900 * Techniques: BIT / Fenwick tree, binary search on BIT, frequency array Problem Link

Quick Revisit

• PROBLEM: Dynamic multiset with add and delete-k-th-smallest, answer any remaining element
• KEY INSIGHT: Bounded values => use a BIT frequency array; k-th element via O(log n) binary search on BIT internals
• TECHNIQUES: Fenwick tree, binary search on BIT, frequency array
• TRANSFER: k-th element in a dynamic collection with bounded values -- BIT beats policy-based trees

First Read

We maintain a multiset. Two operations: add an element $a_i$, or delete the $k$-th smallest element. After all operations, output any remaining element (or 0 if empty). Constraints: up to ${10}^6$ elements and ${10}^6$ operations.

Sounds like "implement an order-statistics tree." My fingers itch to write __gnu_pbds::tree... but let me think if there's something cleaner.

The Policy-Based Detour

My first instinct: use __gnu_pbds::tree<int, null_type, less<int>, ...> -- the policy-based data structure that supports find_by_order (k-th element) and order_of_key. But wait -- it doesn't handle duplicates natively. You'd need to pair each element with a unique index. Doable, but ugly and I've been burned by PBDS corner cases before. Memory is also tight at ${10}^6$ elements.

Let me think differently.

The BIT Insight

What if I think of this as a frequency array? Values go up to ${10}^6$. I keep bit[v] = count of how many copies of value $v$ are in the multiset. Adding: increment bit[a_i]. Deleting the $k$-th smallest: find the smallest $v$ such that $\text{prefix\_sum}(v)\ge k$, then decrement bit[v].

That "find smallest $v$ with prefix sum $\ge k$" is a binary search on a BIT -- a well-known technique. And it runs in $O(\log n)$ per query, same as the BIT itself.

This is cleaner, faster, and avoids all the PBDS headaches.

Binary Search on BIT -- How It Works

The classic approach: don't do lower_bound with repeated query calls (that's $O({\log }^{2}n)$). Instead, walk down the BIT bit by bit:

pos = 0, remaining = k
for bit from high to low:
    if pos + (1 << bit) <= maxVal and bit[pos + (1 << bit)] < remaining:
        remaining -= bit[pos + (1 << bit)]
        pos += (1 << bit)
return pos + 1

The invariant carried across the loop is:

pos is the largest prefix length whose cumulative count is strictly less than the original k, and remaining equals k minus that cumulative count.

So at the end, pos is the largest position with prefix sum below k, and pos + 1 is therefore the first position whose prefix sum reaches k -- i.e., the value of the $k$-th smallest. The walk is $O(\log n)$ -- one pass, no repeated prefix queries. It's essentially the same trick as walking a segment tree, but on the BIT's native binary structure.

Building It

1. BIT of size $\text{MAXVAL}={10}^6$.
2. For add operations: update(a_i, +1).
3. For delete operations: find the $k$-th element via binary search on BIT, then update(that_element, -1).
4. At the end: find any position with nonzero frequency, or output 0.

Implementation Notes

• The BIT binary search must use the internal BIT array (the one with partial sums), not the query function. This is a common source of confusion -- you're reading the Fenwick tree's internal structure directly.
• For the final answer, just do one more kth(1) query if the total count is $>0$.
• Watch the 1-indexing vs 0-indexing. BITs are 1-indexed.

The Code

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1e6 + 1;
int bit[MAXV + 1], n, q;

void update(int i, int v) {
    for (; i <= MAXV; i += i & -i) bit[i] += v;
}

int kth(int k) {
    int pos = 0;
    for (int pw = 1 << 20; pw; pw >>= 1) {
        if (pos + pw <= MAXV && bit[pos + pw] < k) {
            k -= bit[pos + pw];
            pos += pw;
        }
    }
    return pos + 1;
}

int main() {
    scanf("%d%d", &n, &q);
    int total = 0;
    vector<int> a(n), ops(q);
    for (auto& x : a) scanf("%d", &x);
    for (auto& x : ops) scanf("%d", &x);

    for (int x : a) { update(x, 1); total++; }
    for (int x : ops) {
        if (x > 0) { update(x, 1); total++; }
        else {
            int k = -x;
            int val = kth(k);
            update(val, -1);
            total--;
        }
    }
    printf("%d\n", total > 0 ? kth(1) : 0);
}

Transfer Lesson

• k-th element in a dynamic collection -- BIT with binary search on BIT is often simpler and faster than policy-based trees. Requires bounded value range.
• Binary search on the BIT -- walk the internal structure bit by bit. $O(\log n)$ per query, much faster than the $O({\log }^{2}n)$ external binary search approach.
• When PBDS feels like overkill -- ask "can I use a frequency array?" If values are bounded, the answer is usually yes.

---

See also: BIT / Fenwick Tree | Binary Search | Policy-Based DS | DS Selection Guide | Practice Ladder 1700-2100