problem
度度熊正在学习双端队列,他对其翻转和合并产生了很大的兴趣。
初始时有 N 个空的双端队列(编号为 1 到 N ),你要支持度度熊的 Q 次操作。 ①1 u w val 在编号为 u 的队列里加入一个权值为 val 的元素。(w=0 表示加在最前面,w=1 表示加在最后面)。 ②2 u w 询问编号为 u 的队列里的某个元素并删除它。( w=0 表示询问并操作最前面的元素,w=1 表示最后面) ③3 u v w 把编号为 v 的队列“接在”编号为 u 的队列的最后面。w=0 表示顺序接(队列 v 的开头和队列 u 的结尾连在一起,队列v 的结尾作为新队列的结尾), w=1 表示逆序接(先将队列 v 翻转,再顺序接在队列 u 后面)。且该操作完成后,队列 v 被清空。solution
模拟就好。
codes
#includeusing namespace std;int main(){ int n, Q; while(scanf("%d%d",&n,&Q)!=EOF){ deque q[n]; for(int i = 1; i <= Q; i++){ int op; scanf("%d",&op); if(op==1){ int u, w, val; scanf("%d%d%d",&u,&w,&val); if(w==0)q[u-1].push_front(val); else q[u-1].push_back(val); }else if(op==2){ int u, w; scanf("%d%d",&u,&w); if(q[u-1].empty()){ printf("-1\n"); continue; }else{ if(w==0){ printf("%d\n",q[u-1].front()); q[u-1].pop_front(); }else{ printf("%d\n",q[u-1].back()); q[u-1].pop_back(); } } }else if(op==3){ int u, v, w; scanf("%d%d%d",&u,&v,&w); if(w==0){ while(!q[v-1].empty()){ q[u-1].push_back(q[v-1].front()); q[v-1].pop_front(); } }else{ while(!q[v-1].empty()){ q[u-1].push_back(q[v-1].back()); q[v-1].pop_back(); } } } } } return 0;}