Subtask 1

For the first subtask, we can simply use a std::vector (C++) to insert and delete at an index. Then we can iterate through the entire list to count the number of elements that meet the query criteria.

Time Complexity: ~\mathcal O(N \cdot Q)~

Subtask 2

For the second subtask, the problem can be reduced to determining if an element exists in the range ~[l, r]~ of a dynamic array. To support this, we can use an implicit balanced binary search tree to maintain the order of elements, insert at an index, delete at an index, and query a range in ~\mathcal O(\log N)~ time. For the queries, we will store a pointer to the node for each value. To get the current index, we can follow the parent of a node until we reach the root, and add the size of the left subtree if a node is the right child of its parent.

Time Complexity: ~\mathcal O(Q \cdot \log N)~

Subtask 3

Official Solution by Dormi

Similarly to Subtask 2, we can use an implicit balanced binary search tree (BBST) with parent pointers to store the dynamic array. This tree will be known from now on as the main BBST.

Before, we could just store the pointer for each value as each value was distinct. However, now that there can be multiple coins with the same value, we now must use a std::unordered_map (C++) that maps each unique value in the array to a BBST which stores the indices of those values. However, the indices themselves are not stored directly but rather as pointers to their respective nodes on the main BBST. The indices themselves are dynamically determined by walking up from the pointer to the root node of the main BBST. Note that these BBSTs will be known from now on as pointer BBSTs.

We can insert and delete from the main BBST in ~\mathcal O(\log N)~ time and insert and delete from the pointer BBSTs in ~\mathcal O(\log^2 N)~ time since the index of a pointer is calculated in ~\mathcal O(\log N)~.

For queries, we can search for the ~l~ and ~r~ values of the query in the pointer BBST corresponding to its ~x~ value. The final answer is calculated by subtracting the indices of the ~r~ and ~l~ values and then adding ~1~.

Note that while the insert, delete, and query for the pointer BBSTs are standard BBST insert, delete, and queries, the values of each node are calculated dynamically in ~\mathcal O(\log N)~, so the overall complexity of each query is ~\mathcal O(\log^2 N)~.

Time Complexity: ~\mathcal O(Q \cdot \log^2 N)~

Alternate solution by wleung_bvg

First, we will decompose the initial array into blocks of size ~B~. There will be approximately ~\frac N B~ blocks in total. For each block, we will maintain a count of each element using a std::unordered_map (C++), the starting index of each block, and the actual elements (ordered) in each block. For insertions, we will locate the initial block by binary searching over the starting indices of the blocks (this is a very minor optimization over simply iterating through every block). We can then insert an element into the block in a manner similar to subtask 1. Remember to update the count of an element in a block as well as the starting index of all blocks. Assume there will be at most ~C~ elements in a block. Then inserting will take ~\mathcal O(C + \frac N B)~ time. Deletions can be handled in a similar manner. The problem is that after many insertions, ~C~ can become very large. To fix this, when a block becomes larger than ~2 \cdot B~, we can split it into two different blocks in ~\mathcal O(B)~ time. Thus, ~C \in \mathcal O(B)~.

For queries, we can make the observation that each query can be divided into three (possibly empty) sections: a section that is a suffix of a block, a section spanning multiple blocks entirely, and a section that is a prefix of a block (the exception is when a query is contained fully inside a single block). For the sections that are prefixes and suffixes of a block, we can go through every element in that block and count the number of elements meeting the query criteria. This takes ~\mathcal O(B)~ time. For the section spanning multiple blocks, we can iterate through each of those blocks and count the number of elements equal to the query element by using the std::unordered_map for that block. This takes ~\mathcal O(\frac N B)~ time.

Here, it is optimal to choose ~B = \sqrt N~. Note that since std::unordered_map has a bad constant, we should make ~B~ larger than ~\sqrt N~.

There are other variants of this solution, such as splitting a block at the query borders and rebuilding the structure after ~B~ queries. Another variant is to have each block as a fixed size, and use a deque to shift elements to adjacent blocks to maintain the size of each block.

Time Complexity: ~\mathcal O(Q \cdot \sqrt N)~

Bonus Tasks:

As a warm-up, try solving Binary Search Tree Test with the same technique.

If you're up for a challenge, you can try solving Maintaining a Sequence with this technique.