ALLIN1  All in One
Before you begin, you should try this problem! AVL Tree
This problem is simple. Initially, there is a list and it's empty. Then you are given four types of query.
 Insert data to the list
 Remove data from the list
 Print an index (1based) from a specified data after the list was sorted ascendingly
 Print data from a specified index (1based) after the list was sorted ascendingly
Input
Input contains several lines. Each line follows one of these formats.
1 n: Insert n (0 <= n <= 2^{31}  1) to the list
2 n: Remove n from the list. If n was not found, do nothing
3 n: Print n's index (1based) after the list was sorted ascendingly
4 i: Print data on ith index (1based) after the list was sorted ascendingly (0 <= i <= 2^{31}  1)
1: End of input
Output
For each query 3, print n's index in one line. If n was not found, just print 1
For each query 4, print data on ith index in one line. If the index is not valid, just print 1
Example
Input: 3 20
1 Output: 1
hide comments
changyouren:
20211003 13:27:01
scanf is too slow , you should use fread.


andy489:
20210909 19:48:34
"Time limit was set carefully to only accept welldesigned solution." Well what's wrong with the Treap design with Nodes storing count of subtrees and frequency of current key??? 

andy489:
20210909 19:38:47
I am also searchng for a Treap solution. I am getting TLE, but all my queries are log(n). Can anyone share? 

adventurersali:
20200414 20:35:29
Had anyone solved this problem using Treap, it time limits on me. 

zer0_h6cks:
20191203 07:41:41
Can someone help? I'm using splay trees which should be log n amortized but getting TLE. 

nitesh_gupta:
20190930 11:55:57
For 4th query, you have to print 1 if i (given as input) is 0. 

akjol2049:
20181125 10:51:33
do all elements will be distinct? 

hrishabh:
20170509 12:59:44
Can anyone help i am getting time limit exceed, all operations answered in O(1) but still :( .


pandey01:
20170425 13:50:37
Anyone pro here? i need some help...


pvsmpraveen:
20170424 17:01:05
Thank you MIN_25, that helped me!

Added by:  Lucas 
Date:  20170422 
Time limit:  1s1.350s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 