自动搬运

查看原文

来自洛谷，原作者为

	STARSczy 不是奶龙，原神启动，加油

搬运于2025-08-24 22:48:53，当前版本为作者最后更新于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 字节）。