【按值排序的字典】双向链表哈希

全 O(1) 的数据结构

设计一种字典，用来统计键出现的次数（允许插入，删除），同时可以\(O(1)\)返回次数最多和最少的键。

• 如果次数可以是0或负数：

  只需要在一个字典的基础上，记录最大值和最小值，以及对应的键即可。每次插入、删除时同时更新两个最值即可。

• 如果次数为0时需要将键删除：

  删除后需要\(O(1)\)寻回次小的元素（最坏需要连续删除所有元素），这导致我们必须维护全部键的顺序关系，而不是只维护两个最值。

  合适的方法是，在字典的基础上，用一个双向链表维护所有键的顺序，并且字典需要记录每个键对应的节点的指针。每次插入、删除时，对应修改链表的顺序。

  更进一步，每个链表可以记录所有次数相同的键（内部维护一个集合），这样可以严格达到\(O(1)\)。

  class AllOne {
      list<pair<unordered_set<string>, int>> lst;
      unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;
  
  public:
      AllOne() {}
  
      void inc(string key) {
          if (nodes.count(key)) {
              auto cur = nodes[key], nxt = next(cur);
              if (nxt == lst.end() || nxt->second > cur->second + 1) {
                  unordered_set<string> s({key});
                  nodes[key] = lst.emplace(nxt, s, cur->second + 1);
              } else {
                  nxt->first.emplace(key);
                  nodes[key] = nxt;
              }
              cur->first.erase(key);
              if (cur->first.empty()) {
                  lst.erase(cur);
              }
          } else { // key 不在链表中
              if (lst.empty() || lst.begin()->second > 1) {
                  unordered_set<string> s({key});
                  lst.emplace_front(s, 1);
              } else {
                  lst.begin()->first.emplace(key);
              }
              nodes[key] = lst.begin();
          }
      }
  
      void dec(string key) {
          auto cur = nodes[key];
          if (cur->second == 1) { // key 仅出现一次，将其移出 nodes
              nodes.erase(key);
          } else {
              auto pre = prev(cur);
              if (cur == lst.begin() || pre->second < cur->second - 1) {
                  unordered_set<string> s({key});
                  nodes[key] = lst.emplace(cur, s, cur->second - 1);
              } else {
                  pre->first.emplace(key);
                  nodes[key] = pre;
              }
          }
          cur->first.erase(key);
          if (cur->first.empty()) {
              lst.erase(cur);
          }
      }
  
      string getMaxKey() {
          return lst.empty() ? "" : *lst.rbegin()->first.begin();
      }
  
      string getMinKey() {
          return lst.empty() ? "" : *lst.begin()->first.begin();
      }
  };