莫队 + bitset

What · 是什么

莫队 + bitset（Mo's algorithm with bitset）把 bitset 与莫队结合：莫队负责把区间状态（如「哪些权值出现过」）O(1) 地维护成一个 bitset，查询时用位运算（与/或/异或/取反）批量完成常规数据结构难以维护的判定与统计。典型应用：求若干区间的交集元素个数、区间内是否存在两个数的和/差/积/商为某值等（Ynoi 系列大量采用）。

Why · 为什么

How · 实现

伪代码

cnt[v]   # 权值 v 出现次数
b        # bitset: 位 = 权值重编码(权值 + 累计出现次数)
add(v): cnt[v]++; b.set(encode(v, cnt[v]))
remove(v): b.reset(encode(v, cnt[v])); cnt[v]--
# 指针移动（先扩后缩）...
# 回答：把各区间 bitset 做按位或/与，用 popcount 求答案
# 分组：由于一个询问可能涉及多个区间，将询问按块分批，每批重建 bitset

Python 实现

# 说明：Python 无内建 bitset，可用 int 位运算模拟（1<<i 置位、bit_count 统计）。
# 骨架函数：演示 莫队维护“出现过的权值集合” + 三区间交集判定。
# 完整 Ynoi 题（如 P4688）还需：分组控制空间 + 出现次数重编码占位。
def mo_bitset_intersection(n, arr, queries):
    """莫队+bitset 骨架：求三个区间 交集元素个数（判定部分，含多重次数降级为集合）.
    queries: [(l1,r1,l2,r2,l3,r3,id)]. 返回按 id 的交集大小.
    注意：为可运行演示，这里把"出现次数"简化为"出现集合"（去重），
    完整 bitset 重编码见 OI Wiki 参考代码（值+次数 联合编码）。"""
    import math
    block = max(1, int(math.sqrt(n)))
    # 展平三条区间, 每条跑一次莫队收集集合
    intervals = []
    for i, (l1, r1, l2, r2, l3, r3, idx) in enumerate(queries):
        intervals += [(l1, r1, (idx, 0)), (l2, r2, (idx, 1)), (l3, r3, (idx, 2))]
    qs = sorted(intervals, key=lambda q: (q[0] // block, q[1] if (q[0]//block) % 2 == 0 else -q[1]))
    cnt = [0] * (max(arr) + 1 if arr else 1)
    present = set()
    l, r = 0, -1
    collected = {}
    for a, b, k in qs:
        while l > a:
            l -= 1
            cnt[arr[l]] += 1
            present.add(arr[l])
        while r < b:
            r += 1
            cnt[arr[r]] += 1
            present.add(arr[r])
        while l < a:
            cnt[arr[l]] -= 1
            if cnt[arr[l]] == 0:
                present.discard(arr[l])
            l += 1
        while r > b:
            cnt[arr[r]] -= 1
            if cnt[arr[r]] == 0:
                present.discard(arr[r])
            r -= 1
        collected[k] = set(present)
    ans = [0] * len(queries)
    for i, (l1, r1, l2, r2, l3, r3, idx) in enumerate(queries):
        ans[idx] = len(collected[(idx, 0)] & collected[(idx, 1)] & collected[(idx, 2)])
    return ans


if __name__ == "__main__":
    arr = [1, 2, 2, 3, 1]
    qs = [(0, 4, 0, 2, 2, 4, 0), (0, 1, 0, 4, 1, 3, 1)]
    res = mo_bitset_intersection(5, arr, qs)
    assert res == [2, 1], res
    import random
    random.seed(31)
    for _ in range(80):
        n = random.randint(1, 10)
        a = [random.randint(1, 4) for _ in range(n)]
        m = random.randint(1, 10)
        qs = []
        for i in range(m):
            def gen():
                x = random.randrange(n); y = random.randrange(x, n)
                return x, y
            l1, r1 = gen(); l2, r2 = gen(); l3, r3 = gen()
            qs.append((l1, r1, l2, r2, l3, r3, i))
        got = mo_bitset_intersection(n, a, qs)
        for (l1, r1, l2, r2, l3, r3, i) in qs:
            s1 = set(a[l1:r1+1]); s2 = set(a[l2:r2+1]); s3 = set(a[l3:r3+1])
            assert got[i] == len(s1 & s2 & s3), (a, l1, r1, l2, r2, l3, r3, got[i])
    print("All tests passed.")

易错点

• bitset 无法区分重复权值：必须用「权值重编码（值+出现次数）」占位，否则丢多重计数
• 指针移动顺序必须先扩后缩，否则区间为负导致插入负数位（bitset 下标越界）
• 单个大 bitset 空间 1e5×bitset 长度会爆内存：必须将询问按块分批
• Python 的 int.bit_count() 比 bin().count() 快；位宽很大时 int 运算本身开销高
• 合并多个区间 bitset 时注意是「或」还是「与」：三区间交集用与，多个单区间集合用或

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/misc/mo-algo-with-bitset.md
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/misc/code/mo-algo-with-bitset/mo-algo-with-bitset_1.cpp