no tags 

This problem is an extension problem (with a little modification) from this problem: SDITSBST.

In this problem you are given two type of query

  1. Insert an integer to the list.
  2. Given an integer x, you're about to find an integer k which represent x's index if the list is sorted in ascending order. Note that in this problem we will use 1-based indexing.

As the problem title suggest, this problem intended to be solved using Balanced Binary Search Tree, one of its example is AVL Tree.


The first line contains an integer Q, which denotes how many queries that follows.
The next Q lines will be one of the type queries which follow this format:
1 x means insert x to the list
2 x means find x's index if the list is sorted in ascending order.


For each query type 2, print a line containing an integer as the answer or print "Data tidak ada" no quotes if the requested number does not exist in the current lis.


10 1 100 1 74 2 100 2 70 1 152 1 21 1 33 2 100 2 21 2 1 Output: 2 Data tidak ada 4 1 Data tidak ada


Until the third query, the current list is {74, 100}. Therefore you must print 2 as 100 is on the first index.

Arriving at the fourth query we haven't add any other number so the list still consists of {74, 100}. Since 70 is not in the list you must print "Data tidak ada" remember no quotes.

For the last three queries the list looks like this {21, 33, 74, 100, 152}
So the answer for the eighth, ninth, and tenth query respectively are 4, 1, and "Data tidak ada".


1 ≤ Q ≤ 200000

1 ≤ x ≤ 10

It is guaranteed that all integer that inserted in the list will be distinct.


There's no guarantee that the input will results a balanced tree i.e. you have to balanced it yourself :)

hide comments
mhasan01: 2020-07-06 21:15:11

Got Accepted using Treap :)

flyingduchman_: 2019-08-07 21:54:25

You need to keep track of the left_child count and right_child count of each node when inserting, rotating the tree to optimize query type 2, otherwise TLE.

abhimanyu_1998: 2019-04-09 15:49:08


ansisg: 2017-11-04 10:08:24

Last edit: 2017-11-04 10:08:32
mig_143: 2017-07-15 18:42:26

Range of x given in question and in TCs not matching..
1 ≤ x ≤ 10^6 is not correct for TCs
0 ≤ x ≤ 10^6 is correct for TCs

Last edit: 2017-07-15 18:43:08
donbox: 2017-06-28 00:26:16

Seems solvable via Segment tree too. Though i am not getting an AC

Added by:Louis Arianto
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Praktikum Struktur Data D 2015 - Institut Teknologi Sepuluh Nopember