背景:
有些莫队需要 O(1) 移动维护最值或者其它不可删信息,这时候大家就会选择写回滚莫队或者给莫队配上一个值域分块+离散化进行平衡根号复杂度的查询,但是作为一个不想写值域分块的懒人,你有一个耍赖皮的办法:
使用bitset和一个cnt数组,将cnt改成0或从0改成别的数的时候就改bitset对应位置的 01 值,使用bitset的_Find_first 查询第一个 1 就是最值啦,时间复杂度是 O(nn+wnm) 的,一般莫队能过的都能过,同学说 bitset 的findfirst是近似O(1) 的 , 但我感觉如果真是这样且允许离散化的化的化堆就可以退休啦,而且这玩意儿还能查前驱后继,甚至有时候代替set(?),所以估计就是长度除以压位的,但是贼几把快(?),理论上findfirst就是把压位的每个数拿出来 O(1) 判是不是有1?