C. Yet Another Card Deck——（思维）Educational Codeforces Round 107 (Rated for Div. 2)

You have a card deck of n cards, numbered from top to bottom, i. e. the top card has index 1 and bottom card — index n. Each card has its color: the i-th card has color ai.

You should process q queries. The j-th query is described by integer tj. For each query you should:

find the highest card in the deck with color tj, i. e. the card with minimum index;
print the position of the card you found;
take the card and place it on top of the deck.
Input
The first line contains two integers n and q (2≤n≤3⋅105; 1≤q≤3⋅105) — the number of cards in the deck and the number of queries.

The second line contains n integers a1,a2,…,an (1≤ai≤50) — the colors of cards.

The third line contains q integers t1,t2,…,tq (1≤tj≤50) — the query colors. It’s guaranteed that queries ask only colors that are present in the deck.

Output
Print q integers — the answers for each query.

Example
inputCopy
7 5
2 1 1 4 3 3 1
3 2 1 1 4
outputCopy
5 2 3 1 5
Note
Description of the sample:

the deck is [2,1,1,4,3–,3,1] and the first card with color t1=3 has position 5;
the deck is [3,2–,1,1,4,3,1] and the first card with color t2=2 has position 2;
the deck is [2,3,1–,1,4,3,1] and the first card with color t3=1 has position 3;
the deck is [1–,2,3,1,4,3,1] and the first card with color t4=1 has position 1;
the deck is [1,2,3,1,4–,3,1] and the first card with color t5=4 has position 5.

这道题的思路很直接，但是如果硬写，会导致超时。这个时候熟练使用stl库就十分重要了。使用find()函数查找位置，使用rotate()函数实现数组左移（这个函数存在算法优化）。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	vector<int> a(n); //在知道大小时显式构造
	for (int& i : a) scanf("%d", &i); //使用范围for语句直接完成输入

	while (q--)
	{
		int x;
		scanf("%d", &x);
		int p = find(a.begin(), a.end(), x) - a.begin(); //find函数返回指向第一个x的迭代器
		printf("%d ", p + 1);
		rotate(a.begin(), a.begin() + p, a.begin() + p + 1); //范围左闭右开
	}

	return 0;	
}