这是本文档旧的修订版！
线段树分治
算法简介
一种将修改和询问操作转移到线段树上，最后通过遍历线段树求解的离线算法。
算法例题
题意
初始给定 $n$ 个点，图上没有边。现有 $m$ 条边，每条边出现的时间为 $[l_i,r_i]$。询问每个时刻图是否为二分图。
题解
考虑对时间序列建线段树，然后将每条边插入线段树。
遍历线段树，同时使用拓展域并查集动态维护此时是否为二分图。如果当前区间已经不是二分图或者遍历到叶子节点即可得到答案并回溯。
由于修改操作需要支持回溯，所有考虑使用按秩合并的可撤销并查集。
修改次数为 $O(m\log n)$，于是总时间复杂度 $O(m\log^2 n)$。
算法练习
习题一
题意
现有 $n$ 个球员，$m$ 个球迷。每个球员有 $k_i$ 个粉丝。
球迷 $i$ 喜欢球员 $j$ 当且仅当以下两个条件至少有一个满足：
- 球迷 $i$ 是球员 $j$ 的粉丝
- 球迷 $i$ 和 $i'$ 都喜欢球员 $j'$ 且球迷 $i'$ 喜欢球员 $j$
接下来 $q$ 次修改操作，每次修改球迷 $x$ 与球员 $y$ 之间粉丝关系。
每次修改后询问至少需要选择多少个球员才能保证每个球迷至少有一个喜欢的球员。如果没有满足条件的方案，输出 $-1$。
题解
把球员和球迷当成点，粉丝关系视为边，于是题目答案等价于连通块个数减去孤立球员个数。
特殊情况为如果存在孤立球迷，此时答案为 $-1$。
考虑对时间序列建线段树，然后可撤销并查集维护连通块个数、孤立球员个数、孤立球迷个数即可。
时间复杂度 $O\left((q+\sum_{i=1}^n k_i)\log q\log n\right)$。
习题二
题意
有 $n$ 个商店，编号为 $1\sim n$。每个商店有一个价格为 $v_i$ 的特殊商品。接下来 $m$ 个操作：
- 时间流逝一个单位，同时商店 $s$ 额外进货一种价格为 $v$ 的商品
- 给定 $l,r,d,x$ 表示一个顾客的信息，询问该顾客的最大满意度。(满意度等于 $x$ 异或顾客可以购买的商品价格)
记询问时刻为 $t$，该顾客只能在编号为 $[l,r]$ 的商店购物，且只能购买特殊商品或进货时间为 $[t-d+1,t]$ 的商品，问该顾客的最大满意度。
注意初始时刻为 $0$，且询问不会导致时间流逝。
题解
对与区间询问最大异或和操作可以用可持久化字典树 $O(\log v)$ 解决，于是可以先 $O((n+m)\log v)$ 处理出只考虑特殊商品时每个询问的答案。
接下来考虑对时间建立线段树，同时将每个询问加入线段树，遍历线段树时更新答案。
对于修改即进货操作，考虑先对其根据商店编号进行排序，这样就可以使用可持久化字典树加离散化处理询问。
然后遍历线段树时处理完当前节点询问后可以根据修改的时间分配到左右子树处理，每次处理询问重建字典树即可。
时间复杂度 $O((n+m)\log v\log m)$。
