DDOSvoid's Blog

二进制分组

发表于 更新于 分类于
本文字数： 438 阅读时长 ≈ 1 分钟

简介

大概是某种意义上线段树分治和 $cdq$ 分治的替代品

大概就是对于每次的加入操作，我们新建一个分组，如果两个分组的大小相同就将它们合并

容易得到每个点最多被合并 $O(\log n)$ 次，查询的话，容易知道最多同时存在 $O(\log n)$ 组

1
2
3
4
5
6
void insert(char *s) {
    rt[++num] = ++top; sz[num] = 1;
    insert(rt[num], s);
    while (sz[num] == sz[num - 1]) merge(rt[num - 1], rt[num]), sz[num - 1] += sz[num], --num;
    init_fail(rt[num]);
}

例题

  1. 简要题意：有三种操作，操作一向集合中加入一个字符串，操作二从集合中删除一个字符串，操作三给定一个模板串，查询集合中的串在模板串中出现次数的总和

    $len\le 3\times 10^5$

    简要题解：使用二进制分组维护 $AC$ 自动机，合并可以使用线段树合并

    CF 710F String Set Queries