A15858. Recent Actions
编程题
普及/提高-
知识点
题目描述
On Codeforces the "Recent Actions" field shows the last $n$ posts with recent actions.
Initially, there are posts $1, 2, \ldots, n$ in the field (this is in order from top to down). Also there are infinitely many posts not in the field, numbered with integers $n + 1, n + 2, \ldots$ .
When recent action happens in the post $p$ :
- If it is in the "Recent Actions" field, it moves from its position to the top position.
- Otherwise, it is added to the top position, and the post on the down position is removed from the "Recent Actions" field.
You know, that the next $m$ recent actions will happen in the posts $p_1, p_2, \ldots, p_m$ ( $n + 1 \leq p_i \leq n + m$ ) in the moments of time $1, 2, \ldots, m$ . Note, that recent actions only happen with posts with numbers $\geq n + 1$ .
For each post $i$ ( $1 \leq i \leq n$ ), find the first time it will be removed from the "Recent Actions" field or say, that it won't be removed.
Initially, there are posts $1, 2, \ldots, n$ in the field (this is in order from top to down). Also there are infinitely many posts not in the field, numbered with integers $n + 1, n + 2, \ldots$ .
When recent action happens in the post $p$ :
- If it is in the "Recent Actions" field, it moves from its position to the top position.
- Otherwise, it is added to the top position, and the post on the down position is removed from the "Recent Actions" field.
You know, that the next $m$ recent actions will happen in the posts $p_1, p_2, \ldots, p_m$ ( $n + 1 \leq p_i \leq n + m$ ) in the moments of time $1, 2, \ldots, m$ . Note, that recent actions only happen with posts with numbers $\geq n + 1$ .
For each post $i$ ( $1 \leq i \leq n$ ), find the first time it will be removed from the "Recent Actions" field or say, that it won't be removed.
输入格式
The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. Descriptions of test cases follow.
The first line of each test case contains two integers $n$ , $m$ ( $1 \leq n, m \leq 5 \cdot 10^4$ ) — the size of the "Recent Actions" field and the number of actions.
The next line contains $m$ integers $p_1, p_2, \ldots, p_m$ ( $n + 1 \leq p_i \leq n + m$ ).
It is guaranteed, that the sum of $n$ and the sum of $m$ for all test cases does not exceed $5 \cdot 10^4$ .
The first line of each test case contains two integers $n$ , $m$ ( $1 \leq n, m \leq 5 \cdot 10^4$ ) — the size of the "Recent Actions" field and the number of actions.
The next line contains $m$ integers $p_1, p_2, \ldots, p_m$ ( $n + 1 \leq p_i \leq n + m$ ).
It is guaranteed, that the sum of $n$ and the sum of $m$ for all test cases does not exceed $5 \cdot 10^4$ .
输出格式
For each test case print $n$ integers $t_1, t_2, \ldots, t_n$ , where $t_i=-1$ if the post $i$ won't be removed or $t_i$ equals to the first moment of time the post $i$ will be removed ( $1 \leq t_i \leq m$ ).
输入输出样例
输入 #1
10 1 1 2 3 2 5 4 4 5 5 9 9 5 7 5 5 6 7 8 9 10 3 4 4 4 4 4 4 4 5 5 6 6 3 5 4 5 5 5 4 4 20 5 5 24 24 24 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 5 7 7 8 7 11 7 12 10 6 7 8 11 7 8 8 8 12
输出 #1
1 -1 2 1 -1 5 2 1 5 4 3 2 1 -1 -1 1 -1 -1 3 1 -1 2 1 8 7 3 1 7 6 4 2 1 -1 -1 7 3 2 1
说明/提示
In the first test case, the only post $1$ will be removed at the moment $1$ and replaced by the post $2$ .
In the second test case the "Recent Actions" field will be (given an order from top to down):
1. Before moment $1$ : $[1, 2, 3]$ , after moment $1$ : $[5, 1, 2]$ . Post number $3$ was removed.
2. Before moment $2$ : $[5, 1, 2]$ , after moment $2$ : $[4, 5, 1]$ . Post number $2$ was removed.
Post number $1$ won't be removed.
In the third test case the "Recent Actions" field will be (given an order from top to down):
1. Before moment $1$ : $[1, 2, 3, 4]$ , after moment $1$ : $[5, 1, 2, 3]$ . Post number $4$ was removed.
2. Before moment $2$ : $[5, 1, 2, 3]$ , after moment $2$ : $[9, 5, 1, 2]$ . Post number $3$ was removed.
3. Before moment $3$ : $[9, 5, 1, 2]$ , after moment $3$ : $[9, 5, 1, 2]$ . Nothing was changed.
4. Before moment $4$ : $[9, 5, 1, 2]$ , after moment $4$ : $[5, 9, 1, 2]$ . The order was changed.
5. Before moment $5$ : $[5, 9, 1, 2]$ , after moment $5$ : $[7, 5, 9, 1]$ . Post number $2$ was removed.
Post number $1$ won't be removed.
In the second test case the "Recent Actions" field will be (given an order from top to down):
1. Before moment $1$ : $[1, 2, 3]$ , after moment $1$ : $[5, 1, 2]$ . Post number $3$ was removed.
2. Before moment $2$ : $[5, 1, 2]$ , after moment $2$ : $[4, 5, 1]$ . Post number $2$ was removed.
Post number $1$ won't be removed.
In the third test case the "Recent Actions" field will be (given an order from top to down):
1. Before moment $1$ : $[1, 2, 3, 4]$ , after moment $1$ : $[5, 1, 2, 3]$ . Post number $4$ was removed.
2. Before moment $2$ : $[5, 1, 2, 3]$ , after moment $2$ : $[9, 5, 1, 2]$ . Post number $3$ was removed.
3. Before moment $3$ : $[9, 5, 1, 2]$ , after moment $3$ : $[9, 5, 1, 2]$ . Nothing was changed.
4. Before moment $4$ : $[9, 5, 1, 2]$ , after moment $4$ : $[5, 9, 1, 2]$ . The order was changed.
5. Before moment $5$ : $[5, 9, 1, 2]$ , after moment $5$ : $[7, 5, 9, 1]$ . Post number $2$ was removed.
Post number $1$ won't be removed.