自动搬运

查看原文

来自洛谷，原作者为

	fjzzq2002 **

搬运于2025-08-24 21:51:52，当前版本为作者最后更新于2017-04-16 23:17:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本来这题是打算正常构造数据的，结果出现了意外，我的标程常数实在感人，实在要卡掉暴力大概要开100s一个点......然后就只能出随机数据了，并不知道有没有什么神奇算法可以过，就当做良心送分好了。

考虑将时间轴分块，块大小$\sqrt{m}$左右，每一次处理这一块内的询问。

对于这一块内的询问，修改的存在与否都是一样的，除了这一块内的询问和这一块内撤销的询问。

考虑以这一块内的询问和这一块内撤销的询问的插入点作为关键点，这些关键点把当前时间轴分成了若干块，相邻关键点之间建一棵线段树或者平衡树维护标记。

查询的时候查询第一棵线段树，判断第一个关键点的询问是否包含它，包含则更新，依次查询判断。

这个做法复杂度是$O(m\sqrt{m}logm)$的，常数很大，所以并不能跑过暴力...

因为是随机数据，只要把块大小调成$4\sqrt{m}$左右就能跑得很快了。