ORDERSET - Order statistic set
In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations
- INSERT(S,x): if x is not in S, insert x into S
- DELETE(S,x): if x is in S, delete x from S
and the two type of queries
- K-TH(S) : return the k-th smallest element of S
- COUNT(S,x): return the number of elements of S smaller than x
- Line 1: Q (1 ≤ Q ≤ 200000), the number of operations
- In the next Q lines, the first token of each line is a character I, D, K or C meaning that the corresponding operation is INSERT, DELETE, K-TH or COUNT, respectively, following by a whitespace and an integer which is the parameter for that operation.
If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.
For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word 'invalid'.
Input 8 I -1 I -1 I 2 C 0 K 2 D -1 K 1 K 2 Output 1 2 2 invalid
Can be solved with modified AVL
Can be easily solve using pbds. But, should be solved using segment tree for practice purpose.
easy to solve by policy data structure
it's worthy to solve after learning Treap
Getting TLE in java even after using segment trees with coordinate compression.
Submitted solution -> got TLE