Skip to content

11988: 【原1988】圣诞贺卡

题目

题目描述

author: Changcheng Xiao 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1988

问题描述

圣诞节就要到了,小强准备给自己众多的好朋友邮寄圣诞贺卡。之前小强已经写好了\(N\)张贺卡\( (0 \leq N \leq 100,000) \),并且还排好了序。

每张贺卡上都有一个整数\( K (0 \leq K \leq 10,000) \)。随后他继续制作的贺卡,小强可能有四种操作:第一种是在所有贺卡前插入新贺卡; 第二种是在所有贺卡的最后插入新贺卡;第三种是给一个整数\(X\),然后从头到尾寻找写有\(X\)的第一张贺卡,如果存在则丢弃该贺卡; 第四种是给出两个整数\(X\)、\(Y\),寻找第一张写有\(X\)的贺卡,如果其存在,则在其后插入一张写有\(Y\)的新贺卡。

输入格式

第1行为一个整数\(N\),代表初始贺卡个数(\( 0 \leq N \leq 100,000 \))

第2行有\(N\)个正整数,代表\(N\)张贺卡

第3行为一个整数\(M\),代表操作总数(\( 1 \leq M \leq 10,000 \))

第4行到第\(M + 3\)行有\(M\)个操作:

  • A x:给定x,把x插入到队首
  • B x:给定x,把x插入到队尾
  • C x:给定x,如果x存在于队列中的话,删除队列中第一处出现的x
  • D x y:给定x、y,查找第一张写有x的贺卡,如果存在,这个x后面插入y

输出格式

输出共有2行: 第一行是最后一次操作后的贺卡总张数; 第二行输出最后一次操作后队列的所有元素(空格隔开)

样例输入

6
2 3 2 20 3 7 
5
A 0
B 0
C 2
D 9 3
D 3 5

样例输出

8
0 3 5 2 20 3 7 0

样例说明

操作过程:

2 3 2 20 3 7

0 2 3 2 20 3 7
0 2 3 2 20 3 7 0
0 3 2 20 3 7 0
0 3 2 20 3 7 0
0 3 5 2 20 3 7 0

说明

数据规模:\(0 \leq N \leq 100,000, 0 \leq M \leq 10,000\); 时间限制: 1500ms; 内存限制: 50000kb.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!