1. Идея

Нужно смоделировать работу LRU-кэша.

LRU означает Least Recently Used — если кэш переполнен, удаляется элемент, который использовался наиболее давно.

Здесь важно быстро выполнять все действия:

• по ключу находить элемент кэша;
• после GET или успешного PUT делать этот элемент самым недавно использованным;
• при переполнении быстро удалять самый старый элемент;
• в конце вывести ключи в порядке от самого нового к самому старому.

Если хранить кэш просто в массиве или списке, то перемещать элементы и искать по ключу будет слишком медленно.

Поэтому используется стандартная для LRU структура:

• словарь key -> node, чтобы за O(1) находить элемент по ключу;
• двусвязный список, чтобы за O(1) удалять узел из любого места и вставлять в начало.

Начало списка — самый недавно использованный элемент, конец списка — самый давно использованный.

2. Наблюдения

Наблюдение 1. Что происходит при GET

Если ключ есть в кэше:

• нужно вывести значение;
• элемент становится самым недавно использованным.

Значит, найденный узел надо перенести в начало списка.

Если ключа нет, выводим -1, а кэш не меняется.

Наблюдение 2. Что происходит при PUT

Есть два случая.

Случай 1: ключ уже есть

• меняем значение;
• переносим узел в начало списка.

Случай 2: ключа нет

• создаём новый узел;
• вставляем его в начало списка;
• добавляем его в словарь.

Если после этого элементов стало больше c, надо удалить узел с конца списка, потому что он использовался раньше всех.

Наблюдение 3. Почему нужен именно двусвязный список

Нам нужно уметь быстро убрать узел из середины списка и вставить в начало.

Если список односвязный, то для удаления узла пришлось бы искать предыдущий элемент. Это уже не O(1).

В двусвязном списке у узла есть ссылки prev и next, поэтому удаление и вставка выполняются за постоянное время.

Наблюдение 4. Что храним в словаре

В словаре удобно хранить не значение, а указатель на узел списка.

Тогда по ключу можно сразу:

• получить узел;
• прочитать его значение;
• переместить этот же узел в начало списка.

3. Алгоритм

Будем хранить:

• mp — словарь ключ -> узел;
• head — начало списка, самый недавно использованный элемент;
• tail — конец списка, самый давно использованный элемент;
• sz или size — текущее число элементов.

Каждый узел хранит:

• key
• value
• prev
• next

Нужны три вспомогательные операции.

remove_node(node)

Удаляет узел из двусвязного списка.

• Если у узла есть предыдущий, то prev->next = next.
• Иначе этот узел был головой, значит head = next.
• Если у узла есть следующий, то next->prev = prev.
• Иначе этот узел был хвостом, значит tail = prev.

После этого у самого узла обнуляем ссылки.

add_to_front(node)

Добавляет узел в начало списка.

• prev = None
• next = head
• если список не пуст, у старой головы prev = node
• если список был пуст, то этот узел становится и tail
• затем head = node

move_to_front(node)

Если узел уже в начале, ничего делать не нужно.

Иначе:

• удалить его из текущего места;
• вставить в начало.

Далее обрабатываем операции.

Операция GET key

• если key нет в mp, выводим -1;
• иначе:
  • берём узел;
  • переносим его в начало;
  • выводим его value.

Операция PUT key value

• если key уже есть:
  • берём узел;
  • меняем value;
  • переносим в начало;
• иначе:
  • создаём новый узел;
  • вставляем в начало;
  • записываем его в словарь;
  • увеличиваем размер;
  • если размер стал больше c:
    • берём tail;
    • удаляем его из списка;
    • удаляем его ключ из словаря;
    • уменьшаем размер.

Вывод ответа в конце

Проходим по списку от head до tail и собираем ключи.

После этого выводим:

• сначала количество ключей;
• затем сами ключи в порядке от самого недавно использованного к самому давно использованному.

4. Почему это работает

Докажем, что структура всегда правильно хранит состояние LRU-кэша.

Инвариант

После обработки каждой операции:

• в словаре mp находятся ровно все ключи, которые сейчас есть в кэше;
• каждому ключу соответствует его узел в списке;
• список содержит все элементы кэша ровно по одному разу;
• порядок в списке идёт от самого недавно использованного элемента в head до самого давно использованного в tail.

Проверим, что этот инвариант сохраняется.

Изначальное состояние

Кэш пуст:

• словарь пуст;
• список пуст;
• head = tail = None.

Инвариант выполнен.

Операция GET

Если ключа нет

По условию нужно вывести -1, состояние кэша не меняется.

Значит, инвариант сохраняется.

Если ключ есть

Мы находим его узел через словарь. После обращения этот элемент должен стать самым недавно использованным. Именно это и делает move_to_front(node).

Поскольку узел не удаляется из кэша, а только переставляется в начало, множество элементов не меняется. Меняется только порядок, и он становится правильным: только что использованный элемент стоит первым.

Значит, инвариант сохраняется.

Операция PUT

Если ключ уже есть

Мы обновляем значение и переносим узел в начало списка.

Это соответствует условию: элемент считается самым недавно использованным.

Множество ключей не меняется, порядок становится правильным, инвариант сохраняется.

Если ключа нет

Мы создаём новый узел и ставим его в начало. Это правильно, потому что новый элемент только что использован.

Если размер не превышает c, всё корректно.

Если размер стал больше c, нужно удалить наименее недавно использованный элемент. По инварианту это именно tail, то есть последний узел списка. Мы удаляем его и из списка, и из словаря.

Значит, после удаления в структуре остаются ровно те элементы, которые должны быть в LRU-кэше, и в правильном порядке.

Инвариант снова сохраняется.

Вывод

Так как инвариант верен после каждой операции, то после обработки всех запросов:

• все ответы на GET корректны;
• финальный список ключей от head к tail точно совпадает с требуемым порядком от самого недавно использованного к самому давно использованному.

5. Сложность

Пусть q — число операций.

Каждая операция работает за O(1) в среднем:

• поиск в словаре — O(1) в среднем;
• удаление узла из двусвязного списка — O(1);
• вставка в начало — O(1).

Итоговая сложность:

• обработка всех операций: O(q) в среднем;
• финальный проход по списку: O(c).

Общая сложность: O(q + c) в среднем.

Память:

• словарь хранит до c элементов;
• список тоже до c элементов.

Итого O(c) памяти.

6. Код на C++17

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct Node {
    long long key;
    long long value;
    Node* prev;
    Node* next;

    Node(long long k, long long v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

int main() {
    int c, q;
    cin >> c >> q;

    unordered_map<long long, Node*> mp;
    Node* head = nullptr;
    Node* tail = nullptr;
    int sz = 0;

    auto remove_node = [&](Node* node) {
        if (node->prev != nullptr) {
            node->prev->next = node->next;
        } else {
            head = node->next;
        }

        if (node->next != nullptr) {
            node->next->prev = node->prev;
        } else {
            tail = node->prev;
        }

        node->prev = nullptr;
        node->next = nullptr;
    };

    auto add_to_front = [&](Node* node) {
        node->prev = nullptr;
        node->next = head;
        if (head != nullptr) {
            head->prev = node;
        } else {
            tail = node;
        }
        head = node;
    };

    auto move_to_front = [&](Node* node) {
        if (node == head) {
            return;
        }
        remove_node(node);
        add_to_front(node);
    };

    for (int i = 0; i < q; i++) {
        string op;
        cin >> op;

        if (op == "GET") {
            long long key;
            cin >> key;

            auto it = mp.find(key);
            if (it == mp.end()) {
                cout << -1 << '\n';
            } else {
                Node* node = it->second;
                move_to_front(node);
                cout << node->value << '\n';
            }
        } else {
            long long key, value;
            cin >> key >> value;

            auto it = mp.find(key);
            if (it != mp.end()) {
                Node* node = it->second;
                node->value = value;
                move_to_front(node);
            } else {
                Node* node = new Node(key, value);
                add_to_front(node);
                mp[key] = node;
                sz++;

                if (sz > c) {
                    Node* victim = tail;
                    remove_node(victim);
                    mp.erase(victim->key);
                    delete victim;
                    sz--;
                }
            }
        }
    }

    vector<long long> keys;
    Node* cur = head;
    while (cur != nullptr) {
        keys.push_back(cur->key);
        cur = cur->next;
    }

    cout << keys.size();
    for (long long key : keys) {
        cout << ' ' << key;
    }
    cout << '\n';

    cur = head;
    while (cur != nullptr) {
        Node* nxt = cur->next;
        delete cur;
        cur = nxt;
    }

    return 0;
}

7. Код на Python 3

c, q = map(int, input().split())

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

mp = {}
head = None
tail = None
size = 0

def remove_node(node):
    global head, tail

    if node.prev is not None:
        node.prev.next = node.next
    else:
        head = node.next

    if node.next is not None:
        node.next.prev = node.prev
    else:
        tail = node.prev

    node.prev = None
    node.next = None

def add_to_front(node):
    global head, tail

    node.prev = None
    node.next = head
    if head is not None:
        head.prev = node
    else:
        tail = node
    head = node

def move_to_front(node):
    if node is head:
        return
    remove_node(node)
    add_to_front(node)

for _ in range(q):
    parts = input().split()

    if parts[0] == "GET":
        key = int(parts[1])

        if key not in mp:
            print(-1)
        else:
            node = mp[key]
            move_to_front(node)
            print(node.value)
    else:
        key = int(parts[1])
        value = int(parts[2])

        if key in mp:
            node = mp[key]
            node.value = value
            move_to_front(node)
        else:
            node = Node(key, value)
            add_to_front(node)
            mp[key] = node
            size += 1

            if size > c:
                victim = tail
                remove_node(victim)
                del mp[victim.key]
                size -= 1

keys = []
cur = head
while cur is not None:
    keys.append(cur.key)
    cur = cur.next

print(len(keys), *keys)