本题本质是两个有序集合的维护问题:
在大型多人在线角色扮演游戏(MMORPG)中,玩家会频繁打开各种功能界面,如背包、技能、地图、团队和任务等。为了优化内存占用和加快界面响应速度,游戏需要采用界面缓存管理机制。
游戏中的界面分为两类:
可缓存界面:关闭后不会立即销毁,而是暂存到一个大小有限的缓存区中。当玩家再次打开该界面时,可以快速从缓存区恢复,避免重新加载资源。
不可缓存界面:关闭后立即从内存中卸载,下次打开时需要重新创建。
缓存区采用先入先出(FIFO)淘汰策略:当缓存区已满时,新进入缓存区的界面会将最早进入缓存区的界面挤出(从缓存区中移除,彻底卸载)。
给定所有界面的类型、缓存区的容量,以及一系列打开和关闭界面的操作,请你输出操作完毕后的最终状态:
当前打开的界面列表(按打开顺序由早到晚排列)
当前缓存区中的界面列表(按进入缓存区顺序由早到晚排列)
操作规则如下:
打开界面
关闭界面
第一行包含三个整数 n,m,k 分别表示界面种类数、操作序列长度、缓存区容量。
第二行包含 n 个整数 t1,t2,…,tn,其中 ti=1 表示第 i 个界面是可缓存的,ti=0 表示第 i 个界面是不可缓存的。
接下来 m 行,每行描述一个操作:
数据范围:1≤n≤10000,1≤m≤1000000,1≤k≤5000
第一行输出当前打开的界面编号,按打开顺序由先到后排列,以空格分隔。若没有打开的界面,输出 EMPTY。
第二行输出当前缓存区中的界面编号,按进入缓存区的顺序由先到后排列,以空格分隔。若缓存区为空,输出 EMPTY。
输入
4 9 2
1 1 0 1
open 1
open 2
open 3
close 2
close 3
close 1
open 4
open 1
open 4
输出
1 4
2
说明
| 操作 | 打开列表 | 缓存区 | 说明 |
|---|---|---|---|
| 初始状态 | EMPTY | EMPTY | - |
| open 1 | 1 | 打开界面 1 | |
| open 2 | 1 2 | 打开界面 2 | |
| open 3 | 1 2 3 | 打开界面3 | |
| close 1 | 2 3 | 1 | 界面 1 可缓存,进入缓存区 |
| close 2 | 3 | 1 2 | 界面 2 可缓存,进入缓存区 |
| close 3 | EMPTY | 界面 3 不可缓存,直接卸载 | |
| open 4 | 4 | 打开界面 4 | |
| open 1 | 4 1 | 2 | 界面 1 从缓存区恢复 |
| open 4 | 1 4 | 界面 4 已打开,移到队尾 |