可以使用队列模拟所有事件来解决此题。但是队列是先进先出的特性,无法让队列中一个元素离开,所以需要额外的信息来记录队列中当前某一个元素是否有效。本题可以通过记录每次入队时的时间(或者说此次事件的编号),来判断当前一个元素是否有效,每次购买时,检查当前队头元素所记录的时间是否和最后一次入队时间相同,不相同则为无效。如果无效,则直接出队即可。
队列中的人数同样也能用一个额外的变量来记录,入队事件则人数加一,离队事件则人数减一。
米小游是个资深二次元宅宅,这天他去购买二次元限定手办。
米小游来到贩卖现场,发现已经排好了长长的队伍,并且总共有n个手办正在贩卖。大家都需要排队购买,只有在队列最前面的人可以选择购买或者不购买,所有人随时都可以离开队列,离开队列后也可以随时加入队列。米小游时不时会看一眼队列中有多少人,记录了总共q次事件的发生,并且均为以下4种事件:
米小游发现,由于黄牛的存在,当手办个数小于等于m时,处于队列最前面的人一定会把剩余的所有手办全部买走。当手办全部被买走后,队列会立即清空,后续的所有事件都将失效。
米小游想知道,每次查看队列人数时,队列中有多少人。以及最后手办全部卖完或者所有事件结束后,每个参与过排队的人各买了多少个抽赏?(按名字字典序升序输出)
第一行输入三个整数n,m(1≤m≤n≤109),q(1≤q≤2∗105),如题意所示。 接下来q行,首先输入一个整数op(1≤op≤4)表示事件类型: 若事件类型为1或2,则再输入一个长度不超过 10 的只由大小写字母组成的字符串s表示名字;
先输出若干行,每行输出每个查看事件发生时,队列中都有多少人。
再输出事件结束后,每个参与过排队的人各买了多少个手办(名字字典序升序)
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
70 20 13
1 C
1 B
4
2 C
1 A
1 C
2 B
4
1 B
4
3 50
2 A
4
输出
2
2
3
A 70
B 0
C 0