2247. Where a New Copy Would Land

A collection of integers starts empty. Then q operations arrive, one per line:

add v put another copy of v into the collection del v take one copy of v out of the collection pos v print the 0-based index a new copy of v would take

The new copy goes AFTER every copy already equal to v, which pins the answer down when v is already stored. Nothing is actually inserted by a pos.

add 10 add 3 sorted: 3 10 pos 3 -> 1 a new 3 goes after the existing 3, at index 1 pos 10 -> 2 a new 10 goes at the end pos 2 -> 0 pos 11 -> 2

## Rank, index, and why this problem exists next to 2242

Problem 2242 asks for the position v would take if it went AHEAD of its equals, counting from 1. This one asks for the position it takes going AFTER its equals, counting from 0. On a collection with no copy of v the two answers are the same number, and the moment v is stored they differ by the number of copies.

keys 2 2 2 2242 rank 2 -> 1 1 + (nothing strictly below 2) 2247 pos 2 -> 3 after all three copies, at index 3

Both are legitimate and interviews ask for both, usually by the names lower_bound and upper_bound. Reading the wrong one off a structure is the single most common mistake in this whole topic, which is why the statement spells out which end the new copy goes.

## What most people try first

Keeping a real sorted array and reporting where an insertion would land. The answer is right and the maintenance is the problem: every add and every del shifts the tail of the array, which is O(q) per update and up to 2 * 10^10 element moves across 200000 operations. Nothing is ever inserted by a query here, so there is no need to hold the elements in order at all.

## The method

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Compress them, keep a Fenwick tree of how many copies of each compressed value are stored, and then

pos(v) = prefix sum of counts over every position whose value is <= v

The bound is one binary search with a NON-strict comparison, and the prefix sum is one Fenwick walk, so the query is O(log q).

## Why counting is the same as locating

In sorted order, the keys at most v all come before the slot a new copy of v would take, and every key above v comes after it. So the number of keys at most v is exactly how many slots are used up before the new one, and because the index is 0-based that count IS the index. No + 1 is needed anywhere, which is itself worth checking: the 1-based rank of problem 2242 needs one and this does not.

## Cost

O(q log q) time and O(q) memory. A key of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and the index is at most q = 200000.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - A `del v` always names a value with at least one copy currently stored. - Every operation is `add v`, `del v` or `pos v`. - Every value that can ever be stored appears in the input, so the values are known in advance.