主題
題目連結：
題目意譯：
給定一個由介於 1（含）到 m（含）之間的正整數所組成的陣列 queries，你需要根據以下規則來處理所有的 queries[i]（從 i = 0 到 i = queries.length - 1）：
在最一開始，你有一個排列 P = [1,2,3,……,m]。
對於當前的 i 值，找到在 P 中 queries[i] 的位置（索引值從 0 開始數）並將該數移動到排列 P 的開頭。注意到 queries[i] 在 P 中的位置為 queries[i] 的「結果」。
回傳一個包含著所有 queries[i] 之結果的陣列。
限制：
1 ≦ m ≦ 10 ^ 3
1 ≦ queries.length ≦ m
1 ≦ queries[i] ≦ m
範例測資：
範例 1：
輸入： queries = [3,1,2,1], m = 5
輸出： [2,1,2,1]
解釋： queries 將按以下方式處理：
對於 i = 0：queries[i] = 3 、 P = [1,2,3,4,5]，而 3 在 P 中的位置為 2，則我們將 3 移動 P 的開頭使得 P = [3,1,2,4,5]。
對於 i = 1：queries[i] = 1 、 P = [3,1,2,4,5]，而 1 在 P 中的位置為 1，則我們將 1 移動 P 的開頭使得 P = [1,3,2,4,5]。
對於 i = 2：queries[i] = 2 、 P = [1,3,2,4,5]，而 2 在 P 中的位置為 2，則我們將 2 移動 P 的開頭使得 P = [2,1,3,4,5]。
對於 i = 3：queries[i] = 1 、 P = [2,1,3,4,5]，而 1 在 P 中的位置為 1，則我們將 1 移動 P 的開頭使得 P = [1,2,3,4,5]。
因此，包含所有結果的陣列為 [2,1,2,1]。
範例 2：
輸入： queries = [4,1,2,2], m = 4
輸出： [3,1,2,0]
範例 3：
輸入： queries = [7,5,5,8,3], m = 8
輸出： [6,5,0,7,5]
解題思維：
（令 q = queries.length）
模擬即可。
也就是說，每次都掃過一次 P，然後真的把找到的元素挪到開頭。可以看到時間複雜度是 O(m × q)。
不過這不是這次要講的重點。
可以看到模擬的作法中，「找」和「挪」的動作最糟都要 O(m)。有辦法更快嗎？
以範例測資一為例，queries = [3,1,2,1] 、 m = 5。在 queries[0] = 3 時，從 P = [1,2,3,4,5] 轉變為 P = [3,1,2,4,5] 會經歷 3 和 2 交換，然後 3 再與 1 交換兩個動作（雖然也要看實作方式，但是這邊以「從原位交換到新的定位」為主）。
如果原本 [1,2,3,4,5] 就有一個暫存位置，例如說 P = [X,1,2,3,4,5]，而我們就可以直接將 X 和 3 兩者交換位置變成 P = [3,1,2,X,4,5]。如果忽略了「X」，則就會變為原本的 P = [3,1,2,4,5]。當然如果每次都要移除掉「X」也會浪費時間，所以我們等下再想想辦法。我們先繼續這個「塞暫存位置」的想法。
由於這個例子中 q == 4，因此我們可以在一開始就在 P = [1,2,3,4,5] 前面插入 4 個 X 形成 P = [X,X,X,X,1,2,3,4,5]。然後我們用一個陣列 F 來紀錄現在每個數字的索引值。因此現在
F[1] = 4、
F[2] = 5、
F[3] = 6、
F[4] = 7、
F[5] = 8
（以下先不考慮要怎麼算 answers[i]，其中 answers[i] 為 queries[i] 的結果）
好的，現在我們遇到 queries[0] = 3。那要選哪個「X」呢？答案是從左至右的第 q - i - 1 = 4 - 0 - 1 = 3 個（這邊的索引值也是從 0 開始數），因為我們要選的是還沒有被交換過且最靠右的「X」（要靠右是因為先挑左側的會使後面 queries[i] 的數字之順序錯誤）。
因此此時 P 變成了
[X,X,X,3,1,2,X,4,5]
且此時 T[3] 從 6 變成 3，即原本「X」的位置。其餘不變。
接著遇到 queries[1] = 1，則現在要挑的是第 q - i - 1 = 4 - 1 - 1 = 2 個「X」。因此 P 變成了
[X,X,1,3,X,2,X,4,5]
且 T[1] 從 4 變成 2。其餘不變。
接著是 queries[2] = 2，則現在要挑第 4 - 2 - 1 = 1 個「X」。因此 P 變成了
[X,2,1,3,X,X,X,4,5]
且 T[2] 從 5 變成 1。其餘不變。
接著是 queries[3] = 1，則現在要挑第 0 個「X」。因此 P 變成了
[1,2,X,3,X,X,X,4,5]
且 T[1] 從 2 變 0。其餘不變。
OK，那我們要怎麼算 answers[i]？
可以看到在挑第 q - i - 1 個「X」之前的 T[queries[i]] 值（即挪動 queries[i] 這個數字到開頭之間）減去索引值 0（含）到 T[queries[i]]（含）之間所有的「X」之數量即是我們要的 answers[i] 之值。
注意到此時的「X」數量並不一定等於 q - i 個。因此我們需要別的方式統計「X」的數量或是 0 ～ T[queries[i]] 之間「不是 X」的數字個數。
而如果我們把「X」換成 0，其餘的數字換成「1」，則我們要求 0 ～ T[queries[i]] 之間「不是 X」的數字個數就很單純了，因為我們只要求 0 ～ T[queries[i]] 的「數值加總」即可。
再加上我們有 T[queries[i]] 來紀錄每一個數字在哪裡。所以就算數字被替換了，實際上也不影響上面的例子跑的過程。
因此，我們每次與「X」（現以「0」替換）交換的時候需要做以下動作：
1. 求 0 ～ T[queries[i]] 這個區間和，該值減去 1 即為 answers[i]。
2. 將第 q - i - 1 個「X」與 T[queries[i]] 的數字交換，而這會影響若干個區間的總和。因故有 3. 和 4.。
3. 將 T[queries[i]] 這個位置的數值設為 0，並更新相關區間。
4. 將 q - i - 1 這個位置的數值設為 1，並更新相關區間。
5. 將 T[queries[i]] 設為 q - i - 1。
而因為我們要求區間和以及更新位置值 + 區間和，因此我們會需要動用到線段樹（Segment Tree，參見這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
