难得能比较简短地写出来一个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;
}