链接:
来源:牛客网题目描述
ZZT 创造了一个队列 Q。这个队列包含了 N 个元素,队列中的第 i 个元素用 Q i 表示。Q 1 表示队头元素,Q N 表示队尾元素。队列中的元素是 N 的一个全排列。 ZZT 需要在这个队列上执行 P 次操作,操作分两种: FIRST X: 将元素 X 移到队头。 LAST X: 将元素 X 移到队尾。 在 P 次操作之后,ZZT 想知道队列中的元素的排列方式,由于他最近很忙,因此需要请你帮他解决这个问题。
输入描述:
第一行输入一个正整数 N,表示队列的大小。 第二行输入 N 个正整数,Q1
, Q2
, Q3
, ... ..., QN
,Qi
表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。 第三行输入一个正整数 P,表示接下来要进行的操作次数。
接下来 P 行,第 i 行输入一个字符串 S i 以及一个正整数 X i,表示一次操作。
1 ≤ N ≤ 10 5. 1 ≤ Q i ≤ N. 1 ≤ P ≤ 10 5. S i { “FIRST”, “LAST” }. 1 ≤ X i ≤ 10 5.
输出描述:
输出 N 个正整数,表示 P 次操作之后的队列。
示例1
输入
44 2 1 33FIRST 4LAST 2LAST 1
输出
4 3 2 1 题意:中文题很明了了,要求对一长度为n的=队列进行m次操作,将指定元素插在队头或者队尾 题解:我们用两个数组进行保存和一个set容器进行操作 先将数据和操作分别读入 因为我们可以知道,操作从前往后会将数据不断的往队列里面压缩,所以我们将操作存起来倒着操作 这样就可以保证元素的顺序 用set容器来维护,确保临时数组b中没有重复元素出现 代码如下
#includeusing namespace std;#define LL long longconst int maxn=1e5+5;int a[maxn], b[maxn];set s;char ins[maxn][10];int v[maxn];int main(){ int n; scanf("%d", &n); for(int i=0;i =0;i--){ int val=v[i]; if(s.count(val)){ continue; } s.insert(val); if(ins[i][0]=='F'){ b[head++]=val; }else{ b[tail--]=val; } } //我们将a中没有插入到b中的数组插入到b中 for(int i=0;i