【学习笔记】线段树分治

线段树分治用于离线处理一些带有时间属性的操作。最常见的是对于给定的每个操作都只在某个时间区间内存在效力,换言之即每个操作都需要可撤销。

嗯,废话说完了。做法大概就是拿线段树 $+$ vector 维护一下操作区间的所有操作,然后直接在询问里按时间跑分治,顺便在线段树内维护合法修改即可。

一道例题

以下是 $bzoj4025$ :

神犇有一个 $n$ 个节点的图。

因为神犇是神犇,所以在 $\rm T$ 时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。

$1\leq n,m,\rm T\leq 10^6$。

大概就是通过线段树+vector维护每个区间加了哪些边,然后通过可撤销的并查集来维护当前图内是否有奇环。判断过程大概就是如果可以有边加进去就加边,否则判断两者到根的实际距离是否奇偶性相同,如果相同那么添上这条边一定会使得出现一个奇环。

然后这题由于有奇环可以把答案记为 $0$,那么就可以不再递归下去。也算是一个剪枝?

哦对,由于要支持撤销,所以就换成了按 $\rm size$ 合并的并查集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int N = 200010 ;
const int T = 400010 ;

int n, m, k, ans[T] ;
int dis[N], fa[N], sz[N] ;
struct edges{ int u, v ; } ;
vector <edges> S[N * 3], O ;

il int find(int x){
while (x != fa[x])
x = fa[x] ; return x ;
}
il int dist(int x){
int ret = 0 ;
while (x != fa[x])
ret ^= dis[x], x = fa[x] ;
return ret ;
}
void update(int rt, int l, int r, int ul, int ur, int fr, int to){
if (l >= ul && r <= ur)
return S[rt].p_b((edges){fr, to}), void() ;
int mid = (l + r) >> 1 ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, fr, to) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, fr, to) ;
}
void do_do(int rt, int l, int r){
int mid = (l + r) >> 1 ;
bool ret = 0 ; vector<edges>O ;
for (int i = 0 ; i < S[rt].size() ; ++ i){
int u = S[rt][i].u ;
int v = S[rt][i].v ;
int f1 = find(u), f2 = find(v) ;
if (f1 != f2){
if (sz[f1] > sz[f2])
swap(f1, f2), swap(u, v) ;
O.p_b((edges){f1, f2}) ;
fa[f1] = f2, sz[f2] += sz[f1] ;
dis[f1] = dis[u] ^ dis[v] ^ 1 ;
}
else if (dist(u) == dist(v)) { ret = 1 ; break ; }
}
if (!ret)
if (l == r) ans[l] = 1 ;
else do_do(rt << 1, l, mid), do_do(rt << 1 | 1, mid + 1, r) ;
for (int i = O.size() - 1 ; ~i ; -- i)
sz[O[i].v] -= sz[O[i].u], dis[O[i].u] = 0, fa[O[i].u] = O[i].u ;
}
int main(){
int u, v, l, r ;
cin >> n >> m >> k ;
for (int i = 1 ; i <= m ; ++ i){
cin >> u >> v >> l >> r ;
if (l < r) update(1, 1, k, l + 1, r, u, v) ;
}
for (int i = 1 ; i <= n ; ++ i)
fa[i] = i, sz[i] = 1 ; do_do(1, 1, k) ;
for (int i = 1 ; i <= k ; ++ i)
ans[i] ? puts("Yes") : puts("No") ;
return 0 ;
}

然后,然后就没了…

一些拓展

(1)

求不包含元素 $1\sim n$ 的 $01$ 背包。

$1\leq n,m\leq 2000$

直接线段树分治做,第 $i$ 个物品的存在时间是 $1\sim i-1$ 和 $i+1 \sim n$ .

但有个问题就在于每次计算的复杂度都是 $nw$ 的。所以最后复杂度就是 $nw\log n$ 。

(2)

给定一张图,对所有的 $i,j,k$ 求 $i$ 到 $j$ 不经过 $k$ 的⽅案数。

发现朴素地做是 $n^4$ 的。可以通过和上面那题差不多的方法,用线段树分治优化到 $n^3\log n$ 。

结语

其实我关于离线三姐妹的学习顺序是CDQ->整体二分->线段树分治。最后学线段树分治是因为第一次看这个算法感觉很懵…尤其是所有题解都在繁复叨叨那几句话QAQ

总之,句号也是一个新的开始,不是吗?