solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class LFUCache {
   public:
    list<pair<int, list<int>>> Lst;
    unordered_map<int, list<pair<int, list<int>>>::iterator> M1;
    unordered_map<int, list<int>::iterator> M2;
    unordered_map<int, int> VALUE;
    int c;

    void flash(int key) {
        if (M1.count(key) == 0) {
            if (Lst.size() == 0 || Lst.begin()->first != 1) {
                pair<int, list<int>> tmp = {1, {key}};
                Lst.emplace_front(tmp);
                M1[key] = Lst.begin();
                M2[key] = prev(M1[key]->second.end());
            } else {
                auto it = Lst.begin();
                it->second.push_back(key);
                M1[key] = it;
                M2[key] = prev(M1[key]->second.end());
            }
            return;
        }
        auto it1 = M1[key];
        auto it2 = M2[key];
        it1->second.erase(it2);
        if (next(it1) == Lst.end() || next(it1)->first != it1->first + 1) {
            pair<int, list<int>> tmp = {it1->first + 1, {key}};
            M1[key] = Lst.emplace(next(it1), tmp);
            M2[key] = prev(M1[key]->second.end());
        } else {
            next(it1)->second.push_back(key);
            M1[key] = next(it1);
            M2[key] = prev(M1[key]->second.end());
        }
        if (it1->second.size() == 0) {
            Lst.erase(it1);
        }
    }

    void eraseLFU() {
        auto it = Lst.begin();
        auto it2 = it->second.begin();
        debug("eraseLFU", *it2);
        VALUE.erase(*it2);
        M2.erase(*it2);
        M1.erase(*it2);
        it->second.erase(it2);
        if (it->second.size() == 0) {
            Lst.erase(it);
        }
    }

    LFUCache(int capacity) {
        c = capacity;
    }

    int get(int key) {
        debug("get", key);
        if (VALUE.count(key) == 0) {
            return -1;
        } else {
            int ans = VALUE[key];
            flash(key);
            return ans;
        }
    }

    void put(int key, int value) {
        debug("put", key, value);
        if (VALUE.count(key) == 0 && VALUE.size() == c) {
            eraseLFU();
        }
        VALUE[key] = value;
        flash(key);
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */