HDOJ 3436 Queue-jumpers Queue-jumpers

n的範圍很大,但q的範圍比較小.可以把top,query操作用到的點分離出來,沒用到的段縮成點

對于top 把x轉到根,删除後加到開頭位置

對于query 旋轉到根直接輸出

對于rank,遞歸

time limit: 2000/1000 ms (java/others)    memory limit: 32768/32768 k (java/others)

total submission(s): 2216    accepted submission(s): 561

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.

sample input

sample output

author

wzc1989

source