Binary Search Tree Test

View as PDF

Submit solution

Points: 15
Time limit: 2.5s
Java 4.5s
Racket 4.5s
Memory limit: 1G

Problem type

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

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

Each operation is one of the following:

  • I v Insert v into the array.
  • R v Remove a single element from the array with a value of v, if it exists.
  • S v Output the v^{th} smallest element in the array. It is guaranteed that v does not exceed the size of the array.
  • L v Output the index, starting from 1, of the first occurrence of v in the array, if the array was sorted. Output -1 if 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 will be encrypted.

At any time, every element in the array is between 1 and 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) per operation. He practices different data structures every day, but still somehow manages to get them wrong. Will you show him a working example?

Not a binary search tree.

Input Specification

The first line has N and M.

The second line has N integers, the original array.

The next M lines each contain an operation in the format C x, where C is the type of operation. v is encrypted: you should decode it by finding v = x \oplus lastAns, where lastAns is the answer to the previous S or L operation (or 0 if neither operation has occurred). You should perform the operation using v. \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

5 8
9 4 8 11 2
S 4
I 1
S 13
R 10
L 10
L -5
I 8
L 8

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

5 8
9 4 8 11 2
S 4
I 8
S 4
R 2
L 2
L 4
I 9
L 9

Sample Output

4 8 8 9 9 11


  • 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 ?

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


      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

  • 50
    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.

    • 2
      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!

  • 1
    KevinWan  commented on June 22, 2017, 11:27 p.m.

    Can you use a map?

    • 8
      Kirito  commented on June 23, 2017, 4:00 a.m. edited

      You are welcome to use anything, including this.

  • 1
    HUECTRUM  commented on April 3, 2017, 5:00 p.m.

    Is the first test the same as the sample?

    • -9
      ZQFMGB12  commented on April 3, 2017, 5:25 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.