I am currently solving the problem 1915F Greetings from Codeforces Round 918 (Div 4), which involves efficiently performing operations on a sorted set. The task requires inserting elements into a sorted set and then determining the number of elements greater than each newly inserted element (essentially finding the index of the inserted element in the sorted order). Given that n <= 1e5, an O(n^2) solution is infeasible.
In C++, the Policy-Based Data Structures (PBDS) provide a function order_of_key(key) that facilitates efficient operations for such tasks. However, I am working in Java and need an equivalent approach.
Question -
What is the best way to achieve efficient insertions and retrievals of the number of elements greater than a given element in Java? Specifically, how can I implement a solution that maintains O(log n) complexity for both insertions and queries to handle up to 1e5 elements?
I have attempted using tailSet(num).size() and tailMap(num).size(), but both approaches resulted in a time limit exceeded (TLE). Could you suggest a suitable alternative or data structure in Java to meet these requirements and explain its time complexity and implementation details?
Problem Link — https://mirror.codeforces.com/problemset/problem/1915/F
