U414209 租约机制

**时间限制：** 2.0 秒 **空间限制：** 512 MB

鸽鸽用一台土豆机器搭建了自己的博客，一开始只有几百人访问，一台土豆机器的单机系统工作非常流畅。现在有几百万人访问，一台土豆机器无法满足性能需求，给用户的体验很差。鸽鸽准备用多台土豆机器搭建一个分布式土豆系统来提高性能。 不同的用户实际访问的机器是不同的，但是效果必须得是相同。鸽鸽搭建系统时，面临的第一个问题就是，某台机器修改数据后，如何让所有的机器也获取到最新数据。一个朴素的想法，每台机器都存储一份完整的数据，任意一台机器更新数据时都将最新的数据广播给其他机器，让所有机器同时更新。但是这个办法很难保证所有机器都同时更新数据。可能第一台机器更新了数据，第二台机器还没来得及更新数据，在这期间有两个用户分别通过第一台和第二台机器来访问该数据。在这种场景中，两个用户得到的数据就会不一样，一个是新数据，一个是旧数据，这就造成了数据不一致。同时这种方法需要广播数据，性能也较低。鸽鸽想了想，决定只让一台机器作为中心节点可以更新数据，其他机器作为辅助节点可以访问但是无法更新数据。 鸽鸽的这个分布式系统中，有一个中心节点，存储、维护数据。系统中的其他节点通过访问中心节点读取、修改其上的数据。除了中心节点，其他节点初始化是没有数据的。当用户访问到某个节点，请求读取数据时，如果它没有数据就会从中心节点读取数据，然后返回给用户。如果每次用户访问数据，都要从中心节点读取数据，性能比单机系统还差。所以从中心节点获取数据的同时，会获取一个租约时间，**如果当前时间不超过（不大于）租约，就将租约和数据都保存下来**。下次用户访问时，如果**当前时间没有超过租约（租约没到期）**，就**直接返回数据**；否则，先清空现有数据，再**从中心节点读取数据**。聪明的你，肯定想问，如果租约没到期直接返回数据，这个时候中心节点已经更新了数据，不也会出现数据不一致吗？你能想到这个问题，鸽鸽也能想到。所以中心节点在所有节点租约到期前，不会更新数据。中心节点会阻塞所有更新请求，将这些更新请求都按时间顺序保存下来，等**所有租约全部到期后（大于最晚租约的最小时间）**，再一一更新。聪明的你，肯定又想问，那如果一直有其他节点从中心节点获取更晚的租约，那不是会一直无法更新数据？你能想到这个问题，鸽鸽也能想到。所以中心节点在处理完所有更新数据请求前，发送给任何节点的租约只会是**当前已有的最晚租约**，不会更晚。当用户访问某个节点，请求更新数据时，它会把这个请求转发给中心节点。因为**只有中心节点才能更新数据，其他节点只是缓存中心节点的数据**。鸽鸽给自己的这个方法取了个名字，叫租约协议。 再叙述一遍租约协议的读写流程： - 用户读数据：判断数据是否已经存在本地且租约未到期。是，直接返回本地的数据；否，向中心节点发送读取数据和租约请求，读取成功后返回数据，如果租约没到期，则在本地缓存数据； - 用户写数据：被访问节点向中心节点发出写数据请求。中心节点收到写数据请求后，阻塞缓存下来，同时所有新的读数据请求只发放已有最晚的租约。中心节点等待所有租约到期后，一一处理缓存的写请求。 鸽鸽的分布式土豆系统非常神奇，保证时间都是一样的，网络也是永远健康良好的，其他的因素也都是正常可靠的。 给定 $n$ 台机器，编号从 $1$ 到 $n$。其中，$1$ 号机器是中心节点。时间从 $0$ 开始，租约时长为 $k$。假设在 $a$ 时间，向中心节点发出读请求，如果没有需要处理的写请求时，中心节点返回的租约一定是 $a + k$，否则返回已有的最晚租约。中心节点处理一个写请求的时间为 $d$。假设在 $a$ 时间一共有 $D$ 个写请求需要处理，在 $a + D \cdot d$ 时间处理完成。**读操作会立即返回结果，写操作有执行延迟**。 现在有 $m$ 个用户请求，`R t x` 表示在 $t$ 时间向 $x$ 节点发出读数据请求，`W t x` 表示在 $t$ 时间向 $x$ 节点发出写数据请求。对于每个 `R t x` 请求，输出 $x$ 对应的操作：`RWB` 表示从中心节点读取数据和租约，再保存在本地，然后返回给用户；`RB` 表示从中心节点读取数据和租约，发现租约到期，不保存在本地，然后返回给用户；`B` 表示直接从本地读取数据返回给用户。**保证对于同一时间，可能会有多个读请求，但是只会有一个写请求。如果同一时间，同时有读写请求，先处理写请求。保证用户只会直接访问非中心节点**。

无

无

### 样例 1 解释 有 $3$ 个节点，$22$ 个操作，租约时长为 $10$，处理一个写操作时间 $d = 3$ 。 - $0$ 时间，$2$ 和 $3$ 节点数据为空，用户读数据，需要从中心节点获取数据和租约，租约为 $0 + 10 = 10$，当前时间未超过租约，所以需要执行 `RWB` 操作； - $1$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $10$，没有超过租约，用户读数据，直接返回，所以需要执行 `B` 操作； - $10$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $10$，没有超过租约，用户读数据，直接返回，所以需要执行 `B` 操作； - $11$ 时间，$2$ 节点缓存了数据，租约为 $10$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，租约为 $11 + 10 = 21$，当前时间未超过租约，所以需要执行 `RWB` 操作； - $12$ 时间，$2$ 节点向中心节点发送写请求，因为还有租约未超时，所以被阻塞保存下来，将在时间 $22$ 进行； - $20$ 时间，$3$ 节点缓存了数据，租约为 $10$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，因为有写请求未处理完，所以租约为已有最晚租约 $21$，当前时间未超过租约，所以需要执行 `RWB` 操作； - $21$ 时间，$3$ 节点缓存了数据，租约为 $21$，没有超过租约，用户读数据，直接返回，所以需要执行 `B` 操作； - $22$ 时间，最晚租约为 $21$，所有租约过期，中心节点开始处理写请求； - $24$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $21$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，因为有写请求未处理完，所以租约为已有最晚租约 $21$，当前时间超过租约，所以需要执行 `RB` 操作； - $25$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $21$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，因为所有写请求已处理完，所以租约为 $25 + 10 = 35$，当前时间超过租约，所以需要执行 `RWB` 操作； - $40$ 时间，$2$ 节点向中心节点发送写请求，最晚租约为 $35$，所有租约过期，中心节点开始处理写请求； - $43$ 时间，$2$ 节点向中心节点发送写请求，最晚租约为 $35$，所有租约过期，中心节点开始处理写请求； - $43$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $35$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，因为有写请求未处理完，所以租约为已有最晚租约 $35$，当前时间超过租约，所以需要执行 `RB` 操作； - $46$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $35$，超过租约，用户读数据，需要重新从中心节点获取数据和租约，因为所有写请求已处理完，所以租约为 $46 + 10 = 56$，当前时间超过租约，所以需要执行 `RWB` 操作； - $56$ 时间，$2$ 和 $3$ 节点缓存了数据，租约为 $56$，没有超过租约，用户读数据，直接返回，所以需要执行 `B` 操作。 ### 子任务 | 测试点编号 | $n \le$ | $m \le$ | $k \le$ | $d \le$ | 操作说明 | 分数 | | :--------: | :-----: | :-----: | :-----: | :-----: | :--------------------------------: | :--: | | $ 1 $ | $2$ | $10^2$ | $10^2$ | $10^3$ | 无 | $10$ | | $ 2$ | $2$ | $10^2$ | $10^2$ | $10^3$ | 无 | $10$ | | $ 3 $ | $10^2$ | $10^3$ | $10^2$ | $10^3$ | 中心节点修改数据期间不会有用户访问 |$ 10 $ | | $ 4 $ | $10^2$ | $10^3$ | $10^2$ | $10^3$ | 中心节点修改数据期间不会有用户访问 |$ 10 $ | | $ 5 $ | $10^3$ | $10^4$ | $10^2$ | $10^3$ | 没有修改请求 | $ 10 $ | | $ 6 $ | $10^3$ | $10^4$ | $10^2$ | $10^3$ | 没有修改请求 | $10 $ | | $ 7 $ | $10^4$ | $10^5$ | $10^2$ | $10^3$ | 无 | $ 10 $ | | $ 8 $ | $10^4$ | $10^5$ | $10^2$ | $10^3$ | 无 | $ 10 $ | | $ 9 $ | $10^5$ | $10^6$ | $10^2$ | $10^3$ | 无 | $10 $ | | $10 $ | $10^5$ | $10^6$ | $10^2$ | $10^3$ | 无 | $ 10$ |