Luckyleaves's Blog

stay hungry,stay foolish greedy and lucky

bitset

卡常,卡怪神器,支持一大堆牛逼操作。

时间:$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})$(好像还不如暴力)