# Queue-jumpers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

## Problem Description

Ponyo and Garfield are waiting outside the box-office for their favorite movie. Because queuing is so boring, that they want to play a game to kill the time. The game is called “Queue-jumpers”. Suppose that there are N people numbered from 1 to N stand in a line initially. Each time you should simulate one of the following operations:

1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x

Where x is in [1, N].

Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.

## Input

In the first line there is an integer T, indicates the number of test cases.(T<=50)

In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.

## Output

For each test case, output “Case d:“ at first line where d is the case number counted from one, then for each “Query x” operation ,output the current position of person x at a line, for each “Rank x” operation, output the current person at position x at a line.

3
9 5
Top 1
Rank 3
Top 7
Rank 6
Rank 8
6 2
Top 4
Top 5
7 4
Top 5
Top 2
Query 1
Rank 6

Case 1:
3
5
8
Case 2:
Case 3:
3
6

## 题意

Top x：把标号为 x 的人提到队列的第一位；

Query x：查询标号为 x 的人的当前位置；

Rank x：查询当前从左数第 x 个位置的人的标号是多少。

## 分析

Top x：提到队首相当于先把 x 这个节点从树中删除，然后再插入到队首，在 Splay 中可以用一种更加简单的操作来实现。把 x 旋转到根，如果 x 没有左子树，说明已经在队首了，否则把右子树的最左节点旋转到右子树的根，这样旋转完之后，右子树的根节点是没有左子树的，此时再把根（x）的左子树切下来连到右节点的左空位上即可。

Query x：把 x 旋转到根，左子树的 size 加 1 就是根节点当前的序号。

Rank x：查找第 x 个位置的节点号，也是二叉搜索树的基本操作。

Rank 操作的 x 不需要离散化，队列动态变动之后早就不是原本的顺序了。对于这个操作，需要对原本的进行一定改动，每个树节点能够代表的可能是多个队列点，首先用 x-size[sons[spt][0]] 算出要询问的队列点是当前树节点代表的队列点中的第几个，再根据当前树节点代表的队列点区间范围找出原本的序列号。

0%