BZOJ 2453 维护队列

发布于 2017-08-03  235 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2453

题意:单点修改,区间询问权值不同的数的个数。


不带修改直接上莫队就行了,然而带单点修改,怎么办呢?

发现这个修改在传统莫队下是兹词\(O(1)\) 的修改和撤销的,所以考虑到传统莫队移动 l,r 两个指针的基础上加一个 tim 指针,使得每次查询操作时 tim 指针恰好指在合适的版本上即可。

然后考虑块的大小是什么比较优越:

可以被证明的是(偷懒),块大小\(S=n^\frac{2}{3}\) 是比较优越的,此时块数为\(T=n^\frac{1}{3}\) 块

实际上无脑\(\sqrt n\) 还是很稳定的...

 


一个非常弱的准退役OIER