本题作为 T3 其实相对简单，除了读题稍微有点难度之外，实现起来比较简单。

我们可以对每一个缓存行组封装成一个结构体，然后对每一个对象单独操作。

而内部的操作内容本质上是 LRU 算法，这个在 leetcode 都能搜到，利用一个链表记录已有缓存，并且利用一个哈希表记录关键字以及其在链表当中的位置。然后按照 LRU 策略模拟即可。

需要注意的是，我们在数据中卡掉了暴力 LRU 策略的做法，在复刻数据中只能拿到 80 分。有关 LRU 的内容，建议前往 这里 学习。

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <unordered_map>
struct fastIO
{
    static const int BUFF_SZ = 1 << 18;
    char inbuf[BUFF_SZ], outbuf[BUFF_SZ];
    fastIO()
    {
        setvbuf(stdin, inbuf, _IOFBF, BUFF_SZ);
        setvbuf(stdout, outbuf, _IOFBF, BUFF_SZ);
    }
} IO;
inline int rd()
{
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? 0 : f, c = getchar();
    while (c >= '0' && c <= '9') k = (k << 1) + (k << 3) + (c ^ 48), c = getchar();
    return f ? k : -k;
}
inline void wr(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int LIM = (1 << 16) | 10;
inline void read_mem(int x) { putchar('0'), putchar(' '), wr(x), putchar('\n'); }
inline void write_mem(int x) { putchar('1'), putchar(' '), wr(x), putchar('\n'); }
// value : 0 read / 1 write
struct LRUCache 
{
    int sz, lim; // current sz
    std::unordered_map<int, int> cache; // <key, list-ptr>
    // de-list
    struct delist_node
    {
        int k, v; // <key, value>
        int pre, nxt;
    };
    std::vector<delist_node> no;
    std::vector<int> rec;
    int top, cnt;
    int newnode() { return top ? rec[top--] : ++cnt; }
    // notice : clear value flag when recycled
    void recycle(int u) { no[u].k = no[u].v = no[u].pre = no[u].nxt = 0, rec[++top] = u; }
    inline int add_front(int key)
    {
        int u = newnode();
        no[no[0].nxt].pre = u, no[u].nxt = no[0].nxt;
        no[0].nxt = u, no[u].pre = 0;
        no[u].k = key, cache[key] = u;
        return u;
    }
    inline void adjust_to_front(int u)
    {
        no[no[u].pre].nxt = no[u].nxt, no[no[u].nxt].pre = no[u].pre;
        no[no[0].nxt].pre = u, no[u].nxt = no[0].nxt;
        no[0].nxt = u, no[u].pre = 0;
    }
    inline void pop_back()
    {
        int u = no[lim + 1].pre;
        no[lim + 1].pre = no[u].pre, no[no[u].pre].nxt = lim + 1;
        if (no[u].v) write_mem(no[u].k); // value = 1 : write to memory
        cache.erase(no[u].k), recycle(u);
    }
    // LRUCache(int capacity) 
    inline void init(int capacity)
    {
        sz = top = cnt = 0, lim = capacity;
        rec.resize(lim + 2);
        no.resize(lim + 2);
        no[0].nxt = lim + 1, no[lim + 1].pre = 0;
    }
    inline int get(int key) { return cache.count(key) ? (adjust_to_front(cache[key]), no[cache[key]].v) : -1; } 
    inline void put(int key, int value) 
    {
        if (cache.count(key))
            adjust_to_front(cache[key]), no[cache[key]].v |= value;
        else
        {
            // cache miss : read from memory (1.in : write first, and then read)
            if (sz >= lim) pop_back();
            else ++sz;
            read_mem(key);
            int u = add_front(key);
            no[u].v |= value;
        }
    }
} cache[LIM];
int n, N, q, mask;
int bn, bN;
int o, a;
int main()
{
    n = rd(), N = rd(), q = rd();
    bn = __builtin_ctz(n), bN = __builtin_ctz(N), mask = (1 << (bn + bN)) - 1;
    for (int i = 0; i < N; ++i) cache[i].init(n);
    while (q--)
    {
        o = rd(), a = rd();
        int id = (a & mask) >> bn;
        cache[id].put(a, o);
    }
}