偏移量是根号的,也就是 303030 位。但是题解区怎么都用 bitset 写的,而为了压 303030 位用 bitset 多少有点抽象。实际上直接把题解的 bitset 直接改成 long long 甚至 int 都能过。
long long
int
这样的话根据 OI 的经验,把位运算视为 O(1)O(1)O(1),所以本题复杂度应该是 O(p2nn)O(p^2n\sqrt n)O(p2nn) 吧。
感觉题解区用 bitset 都是为了强调压位这个思想,但是用 bitset 压 303030 位多少有点多余吧。
顺带一提本题最优解是面向数据编程老哥,直接改成 int 是除这个以外的最优解。