2026年9月6日，又是一个风和日丽的午后，我没有午睡，而是静静等待Atcoder第七届日本最强学生程序员锦标赛结束，然后趁着比赛完结做一下C题。老实说Atcoder beginner contest 的C题很少会考查一些计算机科学领域的专业算法，但是却有一定思考的深度，需要一些小的tricks才能解决，今天的这题就很有意思，我索性记录一下吧。
C - Remove and Append
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 300 points
Problem Statement
You are given a permutation P=(P1,P2,...,PN) of (1,2,...,N).
For q=1,2,...,Q in this order, perform the following operation.
Remove the element with value a_q from P, and append it to the end of P.
Find the value of each element of P after performing the Q operations.
Constraints
1 <= N <= 2 x 10^5
1 <= Q <= 2 x 10^5
(P1,P2,...,PN) is a permutation of (1,2,...,N).
1 <= a_q <= N
All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
P1 P2 ... PN
a1
a2
...
aQ
Output
Output P1,P2,...,PN after performing the Q operations, in this order, separated by spaces, in one line.
分析：
此题的数据规模来到了10的五次方，如果直接使用Array的delete api，是肯定不行的，因为数组删除元素的时间复杂度是O(n)。因此我们先使用Hash1记录每个元素最开始的坐标，然后采取逆向思维的方式，倒序遍历q次操作后最后一个数字是什么，用Hash2记录它，并把q次操作中出现的元素从Hash1里删除。最后我们再把Hash1的键和Hash2的键的逆序拼接成一个Array输出即可。
n, q = gets.split.map(&:to_i)
in_p = gets.split.map(&:to_i)
h1 = {}
h2 = {}
(0...n).each do |i|
h1[in_p[i]] = i
end
num = []
q.times do
a = gets.to_i
num << a
end
num.reverse_each do |i|
unless h2.key?(i)
h2[i] = 1
h1.delete(i)
end
end
puts (h1.keys + h2.keys.reverse).join(" ")
