Alternative to Policy-Based Data Structures (PBDS) in Java

Правка en1, от RahulAhuja2901, 2024-08-22 21:08:55

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

Теги java, c++, pbds, ordered_set

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский RahulAhuja2901 2024-08-22 21:08:55 1354 Initial revision (published)