卡常,卡怪神器,支持一大堆牛逼操作。
时间:$O(\frac {x}{w})$,x
是原时间,w
是计算机位数。
空间:$O(\frac{x}{w})$,x
是原空间,w
是计算机位数。
这在卡常方面有一大堆有用的效果,尤其在高维偏序有一大堆的应用。
讲点实际的:
P5471 [NOI2019] 弹跳
当然,这题bitset
,肯定是过不了的,但是理论上只要数据范围再良心一点,就没有问题(假掉了,以为$bitset$的单次操作或是$O(1)$ 的)。
思路:首先可以发现,如果我们知道每个点可以跳到哪些点的时候(即边数$n \log n$ 可跑时)最短路就可以解决一切问题,那么我们按照最短路的思路,考虑怎么找到那些点在范围内,我们可以将x
轴和y
轴都建成一颗fhq-treap
,中间用bitset
,存储有哪些点在范围内,两颗bitset
合并出来的结果就是我们所求的,而且bitset
还有一个函数:_Find_first()
,找到从低位到高位的第一个1,之后将找到的数删去即可。
复杂度:$O(n log^2(n) \frac{n}{w} + \frac{n^2}{w})$(好像还不如暴力)