难得能比较简短地写出来一个T3，发现已有题解用链表做的，我是用堆做的，于是简单分享一下。

大体思路还是模拟，关于如何定位是否存在某个编号的内存块，我选择用一个 set ，将关键字设置为块编号，用内置 lower_bound 来实现。还有一点是需要找最近最久未使用，即时间戳最小的一个块，这里还是用一个 set，但是这两个 set 关键字不同，于是乎我开了两个 set 来解决这个问题（）每次修改同时维护即可。

（鄙人陋习，写cp代码不空格）

#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<16)+10;
struct Node1{
	int id,ti;
	bool ch;
	bool operator < (const Node1 &rhs) const {
		return id==rhs.id?ti<rhs.ti:id<rhs.id;
	}
};
struct Node2{
	int id,ti;
	bool ch;
	bool operator < (const Node2 &rhs) const {
		return ti==rhs.ti?id<rhs.id:ti<rhs.ti;
	}
};
int n,N,m,cnt;
set<Node1> s1[maxn];
set<Node2> s2[maxn];
int main() {
	scanf("%d%d%d",&n,&N,&m);
	while(m--) {
		int opt,x;scanf("%d%d",&opt,&x);
		int id=x%(n*N)/n;x++;
		auto it1=s1[id].lower_bound({x,0,0});
		if(it1!=s1[id].end()&&(it1->id)==x) {
			Node1 u=*it1;
			s1[id].erase(it1);
			s1[id].insert({x,++cnt,u.ch||opt});
			auto it2=s2[id].lower_bound({0,u.ti,0});
			s2[id].erase(it2);
			s2[id].insert({x,cnt,u.ch||opt});
			continue;
		}
		if((int)s2[id].size()<n) {
//			printf("==="); 
			printf("0 %d\n",x-1);
			s1[id].insert({x,++cnt,(bool)opt});
			s2[id].insert({x,cnt,(bool)opt});
		}
		else {
			auto it2=s2[id].begin();
			Node2 u=*s2[id].begin();
			if(u.ch) {
//				printf("==="); 
				printf("1 %d\n",u.id-1);
			}
//			printf("==="); 
			printf("0 %d\n",x-1);
			it1=s1[id].lower_bound({u.id,0,0});
			s1[id].erase(it1);
			s1[id].insert({x,++cnt,(bool)opt});
			s2[id].erase(it2);
			s2[id].insert({x,cnt,(bool)opt});
		}
	}
	return 0;
}

本题作为 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);
    }
}