Binary Search Tree Test

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 2.5s

Java 4.5s

Racket 4.5s

Memory limit: 1G

Author:

ZQFMGB12

Problem type

Xyene is doing a contest. He comes across the following problem:

You have an array of $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~ elements. There are $M$ ~M~ $(1 \le M \le 500\,000)$ ~(1 \le M \le 500\,000)~ operations you need to perform on it.

Each operation is one of the following:

I v Insert $v$ ~v~ into the array.
R v Remove a single element from the array with a value of $v$ ~v~, if it exists.
S v Output the $v^{th}$ ~v^{th}~ smallest element in the array. It is guaranteed that $v$ ~v~ does not exceed the size of the array.
L v Output the index, starting from $1$ ~1~, of the first occurrence of $v$ ~v~ in the array, if the array was sorted. Output $-1$ ~-1~ if $v$ ~v~ is not present in the array.

After all of the operations, print out all of the elements remaining in the array in non-decreasing order.

To enforce performing operations in an online manner, $v$ ~v~ will be encrypted.

At any time, every element in the array is between $1$ ~1~ and $10^9$ ~10^9~, inclusive.

Xyene knows that one fast solution uses a Binary Search Tree. However, he knows that a standard binary search tree has a worst case runtime of $\mathcal{O}(N)$ ~\mathcal{O}(N)~ per operation. He practices different data structures every day, but still somehow manages to get them wrong. Will you show him a working example?

$\text{[math]}$

Not a binary search tree.

Input Specification

The first line has $N$ ~N~ and $M$ ~M~.

The second line has $N$ ~N~ integers, the original array.

The next $M$ ~M~ lines each contain an operation in the format C x, where $C$ ~C~ is the type of operation. $v$ ~v~ is encrypted: you should decode it by finding $v = x \oplus lastAns$ ~v = x \oplus lastAns~, where $lastAns$ ~lastAns~ is the answer to the previous S or L operation (or $0$ ~0~ if neither operation has occurred). You should perform the operation using $v$ ~v~. $\oplus$ ~\oplus~ denotes the bitwise XOR operation.

Output Specification

For each S or L operation, output the answer on its own line.

After all operations have been finished, output all of the elements in the final array in non-decreasing order on a single line.

Sample Input

Sample Input (Not Encrypted)

For your convenience, here is a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).

Sample Output

9
8
-1
1
4
4 8 8 9 9 11

Comments

8

yazidue08 commented on Aug. 13, 2018, 2:31 p.m. ← edited →

You said it's welcomed to use map or policy based ds when i sumbited beside ac there is (cheater) and 0 points why ?

14

Kirito commented on Aug. 13, 2018, 5:35 p.m.

Backstory:

A week after ZQFMGB12 uploaded the problem, bruce pointed out that this could be solved using policy-based data structures. So ZQFMGB12 tried to prevent people from using this.

A few weeks later, I managed to get in a submission that used policy-based data structures which avoided detection, rendering it moot.

The Present

Fast-forward a year, and the checker still stands as a relic of the past. The challenge of using policy-based data structures is now in avoiding detection.

Hint: The detection system works by piping your code in through stdin to either a gcc or clang process, which has the flags -E -DONLINE_JUDGE -xc++ -Wall -O2 -lm -march=native -s

51

insignificant commented on July 18, 2018, 1:03 a.m.

The picture says "not a binary search tree", but I checked it at least five times and I swear it's a binary search tree.

4

31501357 commented on April 1, 2020, 12:29 a.m.

Although I'm also fairly sure that is a binary search tree. This problem requires more than a binary search tree to solve, for the select and rank queries, it needs an order statistic tree.

6

Ninjaclasher commented on Aug. 5, 2017, 2:34 p.m.

I don't understand how 4 xor 1 (from the sample input) is equal to 8 (from the decoded sample input). Can someone please explain?

9

wleung_bvg commented on Aug. 6, 2017, 5:14 a.m.

It's xor the last answer, not the last input.

2

Ninjaclasher commented on Aug. 6, 2017, 2:33 p.m.

For some reason, I thought it meant the answer to the last xor operation, which was what confused me. Thanks for the clarification!