题目内容

请实现一个零信任环境下的资源租约管理器。

系统中有若干资源（resourceId）。同一资源在同一时刻最多被一个节点持有。租约有效期为固定的 ttl：若某资源最近一次成功占用/续约时刻为 last，则在半开时间区间 $[\textit{last},\, \textit{last}+\textit{ttl})$ 内租约有效；当查询时刻 time 满足 $\textit{time} \ge \textit{last}+\textit{ttl}$ 时视为过期。

需要实现的接口

• LeaseManager(int ttl)：初始化，租约时长为 ttl（保证 $ttl \ge 1$）。
• acquire(int resourceId, int nodeId, int time)：节点 nodeId 在时刻 time 申请资源。
  • 若该资源当前无有效持有者（不存在或已过期），则分配给 nodeId，记录 last = time，返回 true
  • 若当前有效持有者就是 nodeId，视为续约：更新 last = time，返回 true
  • 否则（被其他节点有效占用），返回 false
• renew(int resourceId, int nodeId, int time)：仅当当前有效持有者是 nodeId 时续约成功（last = time），返回 true；否则 false
• release(int resourceId, int nodeId)：若记录中的持有者是 nodeId（不论是否已过期），清除租约并返回 true；否则 false
• holder(int resourceId, int time)：返回时刻 time 的有效持有者 nodeId；无有效持有者返回 -1
• aliveCount(int time)：返回时刻 time 仍然有效的租约数量

输入描述

每行一次函数调用。首行 LeaseManager(ttl)。累计调用不超过 $3000$ 次。

• $1 \le \textit{ttl} \le 10^9$
• $1 \le \textit{resourceId},\textit{nodeId} \le 10^4$
• $0 \le \textit{time} \le 10^9$

输出描述

• 构造返回 null
• acquire / renew / release 返回 true / false
• holder / aliveCount 返回整数

样例1

输入：

LeaseManager(5)
acquire(1, 10, 0)
acquire(1, 20, 3)
holder(1, 3)
renew(1, 10, 4)
holder(1, 8)
holder(1, 9)
acquire(1, 20, 9)
aliveCount(9)
release(1, 20)
holder(1, 9)

输出：

null
true
false
10
true
10
-1
true
1
true
-1

说明：

• 节点 $10$ 在时刻 $0$ 拿到资源 $1$，有效区间为 $[0,5)$
• 时刻 $3$ 节点 $20$ 抢占失败；holder 仍为 $10$
• 节点 $10$ 在时刻 $4$ 续约，有效区间变为 $[4,9)$
• 时刻 $8$ 仍有效，holder 为 $10$；时刻 $9$ 过期，holder 为 $-1$
• 时刻 $9$ 节点 $20$ 可重新 acquire；随后 release 清空