线段树分治
前言
古人有云，一切恐惧的来源都是火力不足。
所以发展才是硬道理，我又开始补新算法了。
引入
做久了数据结构会发现都有一个共性，即通常会有修改与查询操作（这里说的不太绝对是因为我见识短浅不敢说绝对了）。
那么对于修改操作，通常分为对数据的修改（比如大部分经典板子）和对其它信息的修改（比如维护图上的加边）。这里不提前者，只说后者。
比如我们有三个操作，加入一条边，删除一条边，查询两点是否连通。加入和查询很简单，并查集维护一下即可。但是删除操作很困难，当然我们可以用 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 要好写一点）。