Order statistic set

View as PDF

Submit solution


Points: 0.36 (partial)
Time limit: 0.45s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
© VNOI
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bạn cần quản lý một tập hợp động các số, hỗ trợ hai thao tác cơ bản:

  • INSERT~(S,x)~: nếu ~x~ không thuộc ~S~, thêm ~x~ vào ~S~
  • DELETE~(S,x)~: nếu ~x~ thuộc ~S~, xóa ~x~ khỏi ~S~

và hai loại truy vấn

  • K-TH~(S)~: trả về số bé thứ k của ~S~
  • COUNT~(S,x)~: đếm số lượng số thuộc ~S~ bé hơn ~x~

Input

  • Dòng 1: ~Q~ (~1 \leq Q \leq 200000~), số thao tác
  • ~Q~ dòng sau, đầu mỗi dòng chứa ký tự I, D, K hoặc C cho biết thao tác tương ứng là INSERT, DELETE, K-TH hay COUNT. Tiếp theo là một khoảng trắng và một số nguyên là tham số cho thao tác đó.

Nếu tham số là giá trị ~x~, dữ liệu bảo đảm ~0 \leq |x| \leq 10^9~. Nếu tham số là chỉ số ~k~, dữ liệu bảo đảm ~1 \leq k \leq~ ~10^9~.

Output

  • Với mỗi truy vấn, in ra kết quả tương ứng trên một dòng. Với truy vấn K-TH, nếu ~k~ lớn hơn số phần tử của ~S~, in ra 'invalid'.

Sample Input

8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2

Sample Output

1
2
2
invalid

Comments

Please read the guidelines before commenting.


There are no comments at the moment.