线段树分治
前言
古人有云，一切恐惧的来源都是火力不足。
所以发展才是硬道理，我又开始补新算法了。
引入
做久了数据结构会发现都有一个共性，即通常会有修改与查询操作（这里说的不太绝对是因为我见识短浅不敢说绝对了）。
那么对于修改操作，通常分为对数据的修改（比如大部分经典板子）和对其它信息的修改（比如维护图上的加边）。这里不提前者，只说后者。
比如我们有三个操作，加入一条边，删除一条边，查询两点是否连通。加入和查询很简单，并查集维护一下即可。但是删除操作很困难，当然我们可以用 LCT 维护，但是我不会。这时候就要考虑线段树分治了。
介绍
线段树分治通常用于维护被维护信息存在加入和删除操作的问题。
为了方便叙述，我们就 P5787 二分图 /【模板】线段树分治 来说，但是语言还是会很泛化。
既然你的每条边有加入删除两种操作，那么在时间轴上，它存在的时间就是一个区间。
我们可以立刻想到一个暴力，维护每个时间点上有哪些信息存在，就是对每个时间点开个 vector 存有哪些边，然后对每个时间点求解。
但是直接暴力这样显然时间空间都会爆掉，那么可以考虑像线段树一样，把每个区间分为 $\log n$ 个区间，对线段树上的每个结点维护一个 vector，然后利用类似标记永久化的思路遍历线段树，由于退出结点时需要删除，可以用可撤销并查集维护。这样遍历线段树的时间复杂度为 $O(n+m\log n)$（因为每个区间会被分为 $\log n$ 个区间），然后可撤销并查集的复杂度为 $O(\log m)$（因为每条边只会同时存在一个），总复杂度 $O(m\log n\log m)$，空间复杂度 $O(n+m)$。
例题
P5787 二分图 /【模板】线段树分治
假如你理解了线段树分治你就会发现这道题有多简单，而且因为刚刚也讲过了，在此略过。
P7470 [NOI Online 2021 提高组] 岛屿探险
这道题虽然每个岛不会出现和消失，但是我们分析一下：
对于 $d<b$ 很简单，要计算的就是 $a\oplus c\le d$，把 $a$ 插入 01Trie 后用二元组 $(c,d)$ 去查询。
对于 $d\ge b$ 要计算的就是 $c\oplus a\le b$，发现和上面是对称的，可以把 $c$ 全部插入 01Trie 后用二元组 $(a,b)$ 去给 Trie 打标记，然后再用 $c$ 去统计。
容易发现在对称情况下，每个 $c$ 是会被添加和消除的。由于计数具有可减性，我们可以直接拆成 $[1,l-1],[1,r]$ 两个区间后用 CDQ 分治做（就是一个二维偏序）。但是我们也可以线段树分治后在每个结点上转化为一维偏序。两种方法复杂度均为 $O(n\log n\log V)$（但是有一说一这道题 cdq 要好写一点）。