P2776 题解
积压在做题计划一个多月的题目 （因为我太菜了）
看了题解发现大佬们有用队列做的，蒟蒻表示非常膜拜。
不过，对于需要在数组中间插入元素，首先应该想到的是用链表来做啦！
思路
给大家提供一个用链表的思路。
这里我使用了 list。（STL 大法好）
我们以左边为链表的头，右边为链表的尾。
对于 push 操作，我们需要反向遍历一遍整个 list 链表。
为什么需要反向遍历呢？这样可以在找到同一个组的数时插入待插入数并立刻退出遍历，节省时间。
-
如果找到了一个数的编号和当前待插入的数的编号一样时，将待插入的数插入在当前遍历到的位置的后边。
-
如果遍历完了却找不到，将待插入的数插入在最右边（也就是链表的尾部）。
对于 pop 操作，直接弹出最左边（链表的头部）然后清除就好了。
这么简单？对！就是这么简单！
还有不懂的可以看一下代码~
如果你想尝试正向遍历，可以看看这个。
注意事项
在进行反向遍历时，如果使用了迭代器遍历（也只能用这个，除非你不用 list），在声明迭代器指针时请声明成这样：
list<int>::reverse_iterator it不然会！报！错！
如果不像上面这样声明的话。
代码
接下来是代码时间~
//省略部分头文件
#include<list> //这个头文件要记得打！
using namespace std;
const int N=5e5+10;
int n,m,cnt,cnt2,k;
int a[N];
list<int> form;
int main()
{
cin>>n>>m;
for(int i=0;i<n;++i) cin>>a[i];
cin>>k;
while(k--)
{
string s; int num;
cin>>s;
if(s=="push")
{
cin>>num;bool flag=0;
if(form.empty())
{
form.push_back(num);
continue;
}
for(list<int>::reverse_iterator it = form.rbegin(); it != form.rend();++it) //反向遍历
{
if(a[*it]==a[num])
{
flag=1;
form.insert( it.base() , num );
break;
}
}
if(!flag) form.push_back(num);
}
else
{
cout<<form.front()<<"\n";
if(!form.empty()) form.pop_front();
}
}
return 0;
}