2019 牛客多校第三场 J - LRU management

发表于 更新于 分类于 阅读次数：

题目链接：2019牛客多校第三场J

使用链表来模拟题目中的 Array，这样插入删除都是 \(O(1)\) 的，记录每个元素在内存中的位置，即可以在短时间内查询到某个元素的迭代器，这里我使用 map 从 \(s\) 映射到在链表中对应的迭代器的位置。坑点：01 和 001 不一样，所有的 \(s\) 要在前面加 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T, q, m;
LL s;
struct Node {
    int v;
    LL id;
};
list <Node> lst;
map < LL, list <Node>::iterator > h;
void getInt(LL &x) {
    x = 1; char ch = getchar(); LL sgn = 1;
    while (!isdigit(ch)) { if (ch == '-') sgn = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + (ch ^ 48); ch = getchar(); }
    x *= sgn;
}
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        lst.clear(); h.clear();
        scanf("%d%d", &q, &m);
        int op, v;
        for (int i = 1; i <= q; ++i) {
            scanf("%d", &op); getInt(s); scanf("%d", &v);
            switch (op) {
                case 0: {
                    if (h.find(s) == h.end()) {
                        lst.push_back({v, s});
                        auto it = lst.end(); --it;
                        h[s] = it;
                        if (lst.size() > m) {
                            h.erase(lst.front().id);
                            lst.pop_front();
                        }
                        printf("%d\n", v);
                    } else {
                        int ele = h[s]->v;
                        lst.erase(h[s]);
                        lst.push_back({ele, s});
                        auto it = lst.end(); --it;
                        h[s] = it;
                        printf("%d\n", ele);
                    }
                    break;
                }
                case 1: {
                    if (h.find(s) == h.end()) {
                        puts("Invalid");
                    } else {
                        auto it = h[s];
                        if (v == 0) {
                            it = it;
                        } else if (v == 1) {
                            if (it == lst.end()) it = lst.end();
                            else ++it;
                        } else if (v == -1) {
                            if (it == lst.begin()) it = lst.end();
                            else --it;
                        }
                        if (it == lst.end()) puts("Invalid");
                        else printf("%d\n", it->v);
                    }
                    break;
                }
            }
        }
    }
    return 0;
}