牛客Wannafly 挑战赛19 A【队列Q】

链接：https://www.nowcoder.com/acm/contest/131/A来源：牛客网

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Q _i 表示。Q ₁ 表示队头元素，Q _N 表示队尾元素。队列中的元素是 N 的一个全排列。 ZZT 需要在这个队列上执行 P 次操作，操作分两种： FIRST X: 将元素 X 移到队头。 LAST X: 将元素 X 移到队尾。 在 P 次操作之后，ZZT 想知道队列中的元素的排列方式，由于他最近很忙，因此需要请你帮他解决这个问题。

输入描述:

第一行输入一个正整数 N，表示队列的大小。 第二行输入 N 个正整数，Q₁, Q₂, Q₃, ... ..., Q_N，Q_i 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。 第三行输入一个正整数 P，表示接下来要进行的操作次数。 接下来 P 行，第 i 行输入一个字符串 S _i 以及一个正整数 X _i，表示一次操作。 1 ≤ N ≤ 10 ⁵. 1 ≤ Q _i ≤ N. 1 ≤ P ≤ 10 ⁵. S _i  { “FIRST”, “LAST” }. 1 ≤ X _i ≤ 10 ⁵.

输出描述:

输出 N 个正整数，表示 P 次操作之后的队列。

一道比较有意思的题目，前期一直是正向考虑。然后5%-10%。后来想通了，直接倒着查询，判断这个数最终是放到前面还是后面了，标记一下储存到不同的记录数组，然后按顺序输出即可（FIRST的话是越往后的在前面，LAST的话是越往前越在后面，未标记的按照顺序输出）。

#include<bits/stdc++.h> using namespace std; #define MAXN 1000500 int a[MAXN]; stack<int> sta; string s[MAXN]; int re[MAXN]; int fst[MAXN]; int last[MAXN]; int vis[MAXN]; int ans[MAXN]; int main() { ios::sync_with_stdio(0); int n,q; int cnt=0; int bis=0; int cas=0; int k=0; int num; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } cin>>q; for(int i=0;i<q;i++) { cin>>s[i]>>re[i]; } for(int i=q-1;i>=0;i--) { if(s[i]=="FIRST"&&!vis[re[i]]) { vis[re[i]]=1; fst[cnt++]=re[i]; } else if(s[i]=="LAST"&&!vis[re[i]]) { vis[re[i]]=1; last[cas++]=re[i]; } } for(int i=0;i<n;i++) { if(!vis[a[i]]) ans[bis++]=a[i]; } if(bis||cas) { for(int i=0;i<cnt;i++) cout<<fst[i]<<" "; } else { for(int i=0;i<cnt;i++) { if(i==cnt-1) cout<<fst[i]; else cout<<fst[i]<<" "; } } if(cas) { for(int i=0;i<bis;i++) cout<<ans[i]<<" "; } else { for(int i=0;i<bis;i++) { if(i==bis-1) cout<<ans[i]; else cout<<ans[i]<<" "; } } for(int i=cas-1;i>=0;i--) { if(!i) cout<<last[i]; else cout<<last[i]<<" "; } cout<<endl; return 0; }