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