題目描述

小楊的班級里共有 $N$ 名同學，學號從 $0$ 至 $N?1$。某節課上，老師要求同學們進行列隊。具體來說，老師會依次點名 $M$ 名同學，讓他們加入隊伍。每名新入隊的同學需要先站到隊伍末尾（剛開始隊伍里一個人都沒有，所以第一個入隊的同學只需要站好即可），隨后，整個隊伍中的所有同學需要按身高從低到高重新排序（身高相同的同學之間的順序任意）。

排隊很容易，但重新排序難倒了同學們。稍加討論后，他們發現可以通過交換位置的方法來實現排序。具體來說，他們可以讓隊伍中的兩名同學交換位置這樣整個隊伍的順序就會發生變化，多經過這樣的幾次交換后，隊伍的順序就可以排好。

例如：隊伍中有 $4$ 名同學，學號依次為 $10,17,3,25$，我們可以令 $3$ 號同學和 $10$ 號同學交換位置，則交換后的隊伍順序變為 $3,17,10,25$，這就是一次交換位置。

聰明的小楊想要知道：在老師每次點名一位新同學加入隊伍后，在原有隊伍的基礎上，同學們最少要進行幾次交換位置，才能完成老師按身高排序的要求。

輸入格式

第一行一個整數 $N$，表示同學的數量
第二行 $N$ 個用空格隔開的正整數，依次表示學號為 $0,1,$ … $,N?1$ 的同學的身高（不超過 $2,147,483,647$）。
第三行一個整數 $M$，表示老師點名的數量。
接下來 $M$ 行，依次描述 $M$ 次點名：每行一個整數 $x$（$0\le x<N$），表示要求學號為 $x$ 的同學加入隊伍。保證該名同學此前不在隊伍中。

輸出格式

輸出 $M$ 行，依次表示對于每次點名，同學們最少要進行幾次交換位置，才能完成按身高排序的要求。

輸入輸出樣例 #1

輸入 #1

5
170 165 168 160 175
4
0
3
2
1

輸出 #1

0
1
1
2

輸入輸出樣例 #2

輸入 #2

4
20 20 20 10
4
0
1
2
3

輸出 #2

0
0
0
1

說明/提示

對于所有的測試點，保證 $1\le M\le N\le 2000$。對于 $50\%$ 的測試點，保證所有同學的身高互不相同。

solution

其實是一種插入排序，但是要忽略重復的元素

代碼

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"using namespace std;int a[2000], n, m, x;int main() {set<int> s;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];cin >> m;for (int i = 0; i < m; i++) {cin >> x;int c = 0;for (int p : s) {if (p <= a[x]) {c++;}else{break;}}cout << s.size() - c << endl;s.insert(a[x]);}return 0;
}

結果