思路：模拟

可以使用队列模拟所有事件来解决此题。但是队列是先进先出的特性，无法让队列中一个元素离开，所以需要额外的信息来记录队列中当前某一个元素是否有效。本题可以通过记录每次入队时的时间（或者说此次事件的编号），来判断当前一个元素是否有效，每次购买时，检查当前队头元素所记录的时间是否和最后一次入队时间相同，不相同则为无效。如果无效，则直接出队即可。

队列中的人数同样也能用一个额外的变量来记录，入队事件则人数加一，离队事件则人数减一。

代码

C++

#include <bits/stdc++.h>
using namespace std;

map<string, int> nameToTime;
map<string, int> nameToCount;
queue<pair<string, int>> queueItems;
int countItems;
int n, m, t;

void solve(int quantity) {
    while (!queueItems.empty()) {
        auto [name, time] = queueItems.front();
        if (nameToTime[name] == time) {
            nameToCount[name] += quantity;
            n -= quantity;
            return;
        }
        queueItems.pop();
    }
}

void output() {
    for (auto [name, time] : nameToTime) {
        cout << name << ' ' << nameToCount[name] << endl;
    }
}

int main() {
    cin >> n >> m >> t;
    for (int i = 0; i < t; i++) {
        int op;
        string name;
        cin >> op;
        if (op == 3) {
            int quantity;
            cin >> quantity;
            solve(quantity);
            if (n <= m) {
                solve(n);
                break;
            }
        } else if (op == 1) {
            cin >> name;
            nameToTime[name] = i;
            queueItems.push({name, i});
            countItems++;
        } else if (op == 2) {
            cin >> name;
            nameToTime[name] = -1;
            countItems--;
        } else {
            cout << countItems << endl;
        }
    }
    output();
    return 0;
}

题目描述

米小游是个资深二次元宅宅，这天他去购买二次元限定手办。

米小游来到贩卖现场，发现已经排好了长长的队伍，并且总共有$n$个手办正在贩卖。大家都需要排队购买，只有在队列最前面的人可以选择购买或者不购买，所有人随时都可以离开队列，离开队列后也可以随时加入队列。米小游时不时会看一眼队列中有多少人，记录了总共$q$次事件的发生，并且均为以下4种事件:

1. $1\space s$: 名字为$s$的人加入队列的结尾(保证$s$不在队列中)。
2. $2 \space s$: 名字为$s$的人离开队列(保证$s$在队列中，但不一定在队列最前面)。
3. $3 \space x$: 队列最前面的人购买了$x$个限定手办(保证在手办个数大于$0$时，主当前至少有$x$个手办)。
4. $4$: 米小游查看队列人数。

米小游发现，由于黄牛的存在，当手办个数小于等于$m$时，处于队列最前面的人一定会把剩余的所有手办全部买走。当手办全部被买走后，队列会立即清空，后续的所有事件都将失效。

米小游想知道，每次查看队列人数时，队列中有多少人。以及最后手办全部卖完或者所有事件结束后，每个参与过排队的人各买了多少个抽赏?(按名字字典序升序输出)

输入描述

第一行输入三个整数$n,m(1≤m≤n≤10^9),q(1≤q≤2*10^5)$，如题意所示。 接下来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