题解 P3710 【方方方的数据结构】

· · 题解

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

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

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

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

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

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

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