14368 - 2024_DS_Summer_Lab12_Order of key
|
Time |
Memory |
| Case 1 |
2 sec |
512 MB |
| Case 2 |
2 sec |
512 MB |
| Case 3 |
2 sec |
512 MB |
| Case 4 |
2 sec |
512 MB |
| Case 5 |
2 sec |
512 MB |
| Case 6 |
2 sec |
512 MB |
| Case 7 |
2 sec |
512 MB |
| Case 8 |
2 sec |
512 MB |
| Case 9 |
2 sec |
512 MB |
| Case 10 |
2 sec |
512 MB |
Description
Maintain an integer set S, which support the following operations:
- INS k: Insert k to S. If k is already in S, do nothing.
- DEL k: Delete the element in S with value k. If k is not in S, do nothing.
- ORD k: Find the number of element in S whose value is smaller than or equal to k.
Note: You may use the given template of AVL tree in the slides.
Input
The first line contains an integer q, representing the number of operations. Each of the following q lines is a single operation mentioned above.
Constraint
- 1 <= q <= 3 x 105
- 1 <= k <= 109 for every operation
Subtask
- Testcases 1~5: Only INS and ORD operations
- Testcases 6~10: No further constraints
Output
For each ORD k operations, output the answer in each line.
Tags