题解 CF1623B 【Game on Ranges】（模拟，拓扑排序）

赛场上没看见 \(\sum n\leq1000\)，于是就有个这个 \(O(Tn\log n)\) 的做法。

首先按照区间长度从大到小排序（相当于一次拓扑），然后考虑对于一个区间 \([l_i,r_i]\)，在满足 $len_j

1. 若不存在 \(l_j=l_i\)，则当前取了 \(l_j\) 这个数，分成 \([l_i+1,r_i]\) 一个区间。
2. 若不存在 \(r_j=r_i\)，则当前取了 \(r_j\) 这个数，分成 \([l_i,r_i-1]\) 一个区间。
3. 若同时存在 \(l_j=l_i\) 和 \(r_{j^{\prime}}=r_i\)，则当前取了 \(r_j+1\) 这个数，分成 \([l_j,r_j]\) 和 \([l_{j^{\prime}},r_{j^{\prime}}]\) 两个区间。

因为拓扑排序过，可以用 bfs 进行这个过程，然后每次进行上述 \(3\) 个判断，这些判断可以开两个 vector 维护，初始时将所有区间都塞进去，每次懒惰删除即可。

复杂度瓶颈在排序，不过换成基排之后就能线性。

code