Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 2

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 ${10}^9$. 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 $2^N$ $(1\le N\le 20)$ competitor positions in the tourney tree, numbered $1,2,\dots ,2^N$ 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\le M\le {10}^6)$ commands — see the input format below.

Input Specification

The first line of input contains two integers, $N$ $(1\le N\le 20)$ and $M$ $(1\le M\le {10}^6)$, separated by one space.

The next $2^N$ lines, for $i$ from $1$ to $2^N$, each contain one integer $S_i$, 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 tourney should then be held.
• $W$ means that your program should determine who won the current tourney. Print the position $i$ (between $1$ and $2^N$) 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 Specification

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: