Binary Search Tree Test

View as PDF

Submit solution

Points: 20
Time limit: 5.0s
Java 10.0s
Racket 10.0s
Memory limit: 1G

Problem type

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

You have an array of N (1 \leq N \leq 100\,000) elements. There are M (1 \leq M \leq 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


  • 3
    yazidue08  commented on Aug. 13, 2018, 10:31 a.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 ?

    • 1
      Kirito  commented on Aug. 13, 2018, 1: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

  • 31
    insignificant  commented on July 17, 2018, 9:03 p.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
    Ninjaclasher  commented on Aug. 5, 2017, 10:34 a.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?

    • 4
      wleung_bvg  commented on Aug. 6, 2017, 1:14 a.m.

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

      • 2
        Ninjaclasher  commented on Aug. 6, 2017, 10:33 a.m.

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

  • 0
    KevinWan  commented on June 22, 2017, 7:27 p.m.

    Can you use a map?

    • 6
      Kirito  commented on June 23, 2017, 12:00 a.m.

      You are welcome to use anything, including this.

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

    Is the first test the same as the sample?

    • -6
      ZQFMGB12  commented on April 3, 2017, 1:25 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.

  • -10
    Kirito  commented on Aug. 17, 2016, 9:55 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 0
      ZQFMGB12  commented on Aug. 17, 2016, 12:06 p.m.

      Please read the descriptions for the operations again (in particular for operations R and L). You are forgetting to check something.