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://codeforces.net/problemset/problem/1915/F
You do not need ordered_set to solve this. As the tutorial mentioned, we're counting the number of ranges [a2, b2] which is contained by [a1, b1], which means a1 <= a2 < b2 <= b1
So first, let's sort the pairs by a, this means that the condition a1 <= a2 will always hold, now that it holds, we only need to count the number of b1 which is at least b2, this can be done using any data structure that supports point update, and range sum (segment/fenwick tree will work.)
You could use segment tree or fenwick tree to do this. Even though C++ is much easier, maybe you could make a template for a segment tree with ordered set functions.