题目描述

小华管理一个仓库，支持四种操作：

1. in s：将编号为字符串 s（仅包含小写字母和数字，且各不相同）的产品入库。
2. out：将最晚入库的产品出库，并输出其编号；若仓库空，输出 EMPTY。
3. count：输出当前仓库中产品的数量。
4. check：输出仓库中编号按字典序最小的产品；若仓库空，输出 EMPTY。

要求在 $q\le 2\times10^5$ 次操作内高效完成上述四种操作。

解题思路

数据结构设计

• 栈（stack）：维护入库顺序，用于 out 操作快速取出“最晚入库”产品。
• 最小堆（min‑heap） + 哈希集合（hash set）（Python 方案）
  • check 操作需要快速获取字典序最小者；使用堆顶即可。
  • 由于 out 从栈中删除最新元素，需要在堆中做“懒删除”：出库时只从集合中移除，不立即从堆里删除；check 时弹出堆顶直到它在集合里才输出。
• 平衡二叉搜索树（Java/C++ 方案）
  • 使用 TreeSet（Java）或 std::multiset（C++）维护所有在库编号，支持插入、删除、取最小均为 $O(\log n)$。

操作实现

1. in s
   • 栈 push(s)；集合/树插入 s；堆 push(s)（Python）。
2. out
   • 如果栈空，输出 EMPTY；否则栈顶 pop() 得到编号 s，并从集合/树中删除，输出 s。
3. count
   • 输出集合/树的大小。
4. check
   • Python：弹出堆顶直到该编号在集合中或堆空；若堆空输出 EMPTY，否则输出堆顶但不弹出。
   • Java/C++：若树为空输出 EMPTY，否则输出 first()/*begin()。

复杂度分析

• Python（堆 + 哈希集合）：
  • in：$O(\log n)$（堆）
  • out：$O(1)$（栈） + $O(1)$（集合）
  • check：均摊 $O(\log n)$（堆）
• Java/C++（栈 + 平衡树）：
  • 所有操作均为 $O(\log n)$（插入/删除/查找/取最小）或 $O(1)$（栈）
• 总体时间复杂度 $O(q\log q)$，空间复杂度 $O(q)$。

代码实现

Python

import sys
import heapq

def main():
    input = sys.stdin.readline
    q = int(input())
    stack = []
    min_heap = []
    in_set = set()
    
    for _ in range(q):
        op = input().split()
        if op[0] == 'in':
            s = op[1]
            stack.append(s)            # 记录入库顺序
            heapq.heappush(min_heap, s)  # 用于 check
            in_set.add(s)              # 在库集合
        elif op[0] == 'out':
            # 出库最晚入库的产品
            if not stack:
                print('EMPTY')
            else:
                s = stack.pop()
                in_set.remove(s)
                print(s)
        elif op[0] == 'count':
            print(len(in_set))
        elif op[0] == 'check':
            # 查询字典序最小
            while min_heap and min_heap[0] not in in_set:
                heapq.heappop(min_heap)
            if not min_heap:
                print('EMPTY')
            else:
                print(min_heap[0])

if __name__ == '__main__':
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        Deque<String> stack = new ArrayDeque<>();
        TreeSet<String> tree = new TreeSet<>();

        for (int i = 0; i < q; i++) {
            String[] parts = br.readLine().split(" ");
            String cmd = parts[0];
            if (cmd.equals("in")) {
                String s = parts[1];
                stack.push(s);     // 入栈记录顺序
                tree.add(s);       // 树集维护字典序
            } else if (cmd.equals("out")) {
                // 出库最晚入库的产品
                if (stack.isEmpty()) {
                    System.out.println("EMPTY");
                } else {
                    String s = stack.pop();
                    tree.remove(s);
                    System.out.println(s);
                }
            } else if (cmd.equals("count")) {
                System.out.println(tree.size());
            } else if (cmd.equals("check")) {
                if (tree.isEmpty()) {
                    System.out.println("EMPTY");
                } else {
                    System.out.println(tree.first());
                }
            }
        }
    }
}

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    vector<string> stack_;
    multiset<string> ms;

    while (q--) {
        string cmd;
        cin >> cmd;
        if (cmd == "in") {
            string s;
            cin >> s;
            stack_.push_back(s);  // 记录入库顺序
            ms.insert(s);         // multiset 维护字典序
        }
        else if (cmd == "out") {
            // 出库最晚入库的产品
            if (stack_.empty()) {
                cout << "EMPTY\n";
            } else {
                string s = stack_.back();
                stack_.pop_back();
                ms.erase(ms.find(s));
                cout << s << "\n";
            }
        }
        else if (cmd == "count") {
            cout << ms.size() << "\n";
        }
        else if (cmd == "check") {
            if (ms.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << *ms.begin() << "\n";
            }
        }
    }
    return 0;
}

题目内容

小华是一个仓库管理员，他的日常就是管理仓库产品的入库出库。

有四种操作：

$in$ $s$，给一个只包含小写字符和数字的字符串 $s$ ，表示一个新的产品入库， 产品编号为 $s$ 。

$out$ ，表示一个出库请求，小华会将最晚入库的产品出库。

$count$ ，表示清点仓库里的产品数量。

$check$ ，表示查询仓库里编号字典序最小的产品。(字典序的顺序是先按照 第一个字符以升序排列;如果第一个字符一样，那就比较第二个、第三个 乃至后面的字母。如果比到最后两个串不一样长(比如，$123$ 和 $12345$ )，那么把短者排在前。)

输入描述

第一行一个整数 $q(1<=q<=200000)$ 表示操作的次数。

接下来 $q$ 行每行一个操作，为四种操作之一。

保证所有产品的编号都是仅包含数字和小写字母的字符串，每个字符串长 度不超过 $20$ 。

保证所有产品的编号互不相同。

输出描述

对于每个 $out$ 操作，输出一行，包含一个字符串，表示被出库的产品编号。

如果没有能出库的产品输出 $EMPTY$ 。

对于每个 $count$ 操作，输出一行，包含一个整数，表示当前仓库里的产品 数量。

样例1

输入

13
check
in c1
in c2
count
check
in b3
in b4
count
check
out
check
out
check

输出

EMPTY
2
c1
4
b3
b4
b3
b3
c1

说明

首先 $check$ 操作，此时仓库里没有产品输出 $EMPTY$。

后面 $in$ $c1$ $in$ $c2$ 两个操作，仓库中有 $c1$ ，$c2$ 两个产品，因此 $count$ 操 作，输出为 $2$ 。

$check$ 输出仓库里编号字典序最小的产品编号 $c1$。

然后 $in$ $b3$ $in$ $b4$ ，仓库中有 $c1，c2，b3，b4$ 四个产品，$count$ 操作输出 $4$ ，$check$ 输出仓库里编号字典序最小的产品编号 $b3$ ，$out$ 将最晚入 库的产品出库，输出 $b4$ ，$check$ 输出仓库里编号字典序最小的产品编号 $b 3$ 。$out$ 将最晚入库的产品出库，输出 $b3$ ，此时仓库只有 $c1，c2$ 两个 产品，$check$ 输出仓库里编号最小的产品编号 $c1$ 。