线段树分治
泛化ψ(｀∇´)ψ
有一类问题的操作有以下的特征：
- 一个操作只对 \([l, r]\) 这段时间有效。
- 每次单点询问某一个时间的答案。
利用一种名为线段树分治的思想可以把这个过程优化到 \(O(f \times n \log n)\)。
其中 \(f\) 为计算/撤销一次贡献的时间复杂度。
具体来说我们对时间轴建立线段树，然后把操作用 std::vector 一类的东西挂到对应的 \(O(\log n)\) 个区间上。
最后递归整颗线段树，遍历到一个节点的时候执行操作，递归到叶子的时候检查这个时间的答案，然后回溯撤销掉操作。
例题ψ(｀∇´)ψ
神犇有一个 \(n\) 个节点的图。
因为神犇是神犇，所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。
神犇要求出每一时间段内这个图是否是二分图。
这么简单的问题神犇当然会做了，于是他想考考你。
输入格式
第一行三个整数 \(n,m,k\)。
接下来 \(m\) 行，每行四个整数 \(x,y,l,r\)，表示有一条连接 \(x,y\) 的边在 \(l\) 时刻出现 \(r\) 时刻消失。
输出格式
\(k\) 行，第 \(i\) 行一个字符串
Yes或No，表示在第 \(i\) 时间段内这个图是否是二分图。\(n,k = 10^5\)，\(m = 2\times 10^5\)。\(1 \le x,y \le n\)，\(0 \le l \le r \le k\)。
扩展域并查集可以通过记录黑白染色临域的信息来判断是否是二分图，加上一个可撤销就能维护这个操作了。
非常简单，时间复杂度 \(O(n\log^2 n)\)。
代码不放了，我摆了。
最后更新:
September 27, 2023