题解：P9494 「SFCOI-3」进行一个走的行

STARSczyy · 2024-06-22 12:06:05 · 题解

突进 3 秒，最优解，题解以纪念。

先定一个大的框架。容易想到离线后差分，然后再用平衡树扫一遍，对于每次行走，在 l_i 位置加入，在 r_i+1 位置删去，最后再输出答案。

当平衡树扫到位置 i：

• 若 r_i\not=-1，把平衡树分裂成三段，中间那一段是 [l_i,r_i]，中间一段打上懒标记即可。

• 若 r_i=-1，把平衡树分裂成 [0,l_i] 和 (l_i,inf) 两段，把 (l_i,inf) 一段减去 l_i，此时使用交织区间平衡树合并，单次是可以均摊到 \log n \log V 的（参考1，参考2）。

故总时间复杂度为 n \log n \log V。但实际表现很像 n \log n。

听别人说码风有点差，代码就放云剪贴板了，也算一种防抄袭吧。链接。目前最优解，应该是最短的代码（有压行，但保证每行长度不超过 100 字节）。