2013 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Tourney

Don Cherry has been hired to run 24-hour coverage of a series of single-elimination, bracket-style, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between 1 and 109. In every head-to-head match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guaranteed that, at any time, the skill levels of all competitors are distinct, so there are no ties.

There are 2N (1 ≤ N ≤ 20) competitor positions in the tourney tree, numbered 1, 2, ..., 2N from left to right. In the first round, competitors 1 and 2 face off in a furniture disassembly race, as do competitors 3 and 4, etc. In each subsequent round, the winners of the first two matches from the previous round compete, as do the winners of the following two, etc. After N rounds, a single winner remains. For example, when N = 2, the tourney tree looks like this:

where A represents the winner of the match between competitors 1 and 2, B represents the winner of the match between competitors 3 and 4, and C represents the winner of the match between A and B. The winner of this tourney is C.

Because of sponsorship contracts, some competitors will be replaced over time. After any new person comes in, a new tourney is held.

In order to help Don Cherry, you must write a program to compute certain tourney statistics at various points in time, given a sequence of M (1 ≤ M ≤ 106) commands — see the input format below.

Input

The first line of input contains two integers, N (1 ≤ N ≤ 20) and M (1 ≤ M ≤ 106), separated by one space.

The next 2N lines, for i from 1 to 2N, each contain one integer Si, indicating the skill level of the initial competitor at position i in the tourney tree.

Each of the following M lines will be a command in one of three formats:

  • R i S means that the competitor at position i is removed, and replaced with a new one with skill level S. A new tourney should then be held.
  • W means that your program should determine who won the current tourney. Print the position i (between 1 and 2N) of this competitor.
  • S i means that your program should print out the number of rounds that the competitor at position i won in the current tourney.

Output

For each W or S i command in the input, print out the corresponding integer on a line by itself.

Sample Input

2 8
30
20
10
40
S 1
W
R 4 9
S 4
W
R 2 35
S 2
W

Sample Output

1
4
0
1
2
2

Explanation

The results of the initial tourney are as follows:

As can be seen, competitor 1 wins 1 match, and competitor 4 wins the entire tourney. After this, competitor 4 is replaced by a new competitor with skill level 9. As can be seen below, this causes a different outcome for the tourney held after the third command:

Finally, the state of the tourney tree after the next competitor replacement (caused by the sixth command) is:

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 10.00s
Memory Limit: 512M
Added: May 19, 2013
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...