ORDERSET - Order statistic set

维护一个支持以下操作的动态数组S： - 将x插入S（INSERT(S,x)） 如果x不在S里，将x插入S。 - 从S中删除x（DELETE(S,x)） 如果x在S里，从S中删除x。 - 查询S中第k小的元素（K_TH(S)） 返回S中第k小的元素。 - 计数（COUNT(S,x)） 返回S中小于x的元素个数 # 输入输出格式 ## 输入格式 第一行：一个正整数Q，表示操作数目。 接下来Q行：一个字符，表示操作（I、D、K、C），即INSERT,DELETE,K_TH,COUNT的缩写和一个整数，整数为对应操作的参数。 保证$ 0 \leq \left|x\right|\leq 10^{9} $，$ 1 \leq k \leq 10^{9} $。 ## 输出格式 对于每个查询，输出一行一个数表示结果。 如果K操作中$ k>S $中元素个数，输出一行"invalid"（不带引号） =5088)

[English](/problems/ORDERSET/en/) [Vietnamese](/problems/ORDERSET/vn/)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| ≤ 10 $ ^{9} $ . If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 10 $ ^{9} $ .

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'.

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

1
2
2
invalid