线段树分治

20171202上课时的讲述

​ 以时间为顺序建立一颗线段树，每一个节点开一个$vector$，把一个修改按照其作用区间，$push\;back$到所有“定位”节点上。那么对于一个询问而言，它所受影响的所有修改一定是从线段树根节点到询问的这篇叶子的所有途径节点。

​ 于是我们对于每一个节点上的修改信息进行整合，再一个一个贡献。如此一来，无论添加还是修改，都只是对应一段作用区间而已。所以最后只要在线段树上$DFS$一次即可.

​ 如果有排序操作，最好在区间外面实现有序（排好序）

​ 其实线段树分治重要在思想，而是不是以时间为“轴”是不一定，这个应该因题目而灵活选取。

例题一 YZOJ 2758

【题目描述】

给定一颗树，树的每一条边上有权值上下界（即通过时使用的权值必须在这个上下界的闭区间内，否则无法通过），现在有若干询问，每一个询问给出一个权值$val$,对于每一个询问求一个最长的符合上下界要求的简单路径，输出路径的长度。

【分析与解】

​ 我们按照权值作为线段树的“轴”，那么每一个询问对应到线段树的一个叶节点，而修改操作为线段树的一些区间。于是我们可以先把所有的修改和询问在相应的节点上打标记（$vector$中$push\;back$）.

​ 关于维护当前连边的最长链。我们用并查集来维护这个关系。但是我们注意到，每一条边只能在回答当前的节点时被使用。所以我们要对于并查集每一步操作记录信息（之前的$fa$，更改后的$fa$诸如此类的），在遍历完整个线段树子树后，进行栈序撤销。

练习一 FJOI 2015 火星商店问题

【题目描述】

现在要求实现两种事件：
① $0\; s \;v$​​ 表示第$s$​​个盒子添加了一种价格为$v$​​商品

② $1\; L\; R\; x\; d $表示询问在前后的$d$天内，$[L,R]$的盒子的所有商品中，其价格异或$x$的最大值

每一天先有$0$事件，再有$1$事件

【分析与解】

​ 通过“可持久化Trie”树的学习，我们知道关于异或最大值这件事可以通过查询$root[L-1]$到$root[R]$中的与$x$的二进制相异的最大的那个“单词”来得到。

​ 但是天数是一个范围，也就是说我们相当于树的个数可能是二维的。

​ 线段树分治要求询问转化成若干线段树式节点的查询，修改也是如此。

​ 于是我们把时间作为线段树的下标“轴”（外部实现），把可持久化$Trie$作为内部实现。

​ 对于每一个线段树节点，我们维护两个vector，分别表示“途径”该节点的所有修改操作的编号，和“定位”该节点的所有查询的操作的编号。

​ 在$main$函数中，我们把修改和查询操作依次添加到线段树的相应节点的$vector$中。注意，修改操作是所有的途径节点，查询操作仅仅在定位节点中添加即可。在线段树分治函数中，我们先访问大区间，再访问小区间（其实这道题怎么都行，因为所有的节点是独立贡献，顺序无所谓（方法一），但是遇到$DFS$序之类的问题，就必须这么做了（方法二））。然后在每一个节点，先处理修改（依次添加$Trie$树信息），再处理询问，更新答案。

​ 复杂度为$O(klog_n)$ 其中$k$是处理每一个修改的复杂度，大概也是什么的$log$。

练习二 TJOI2018 数学计算

【题目描述】

给定$mod$，要求对每一个时刻支持两种操作：

① $1 \;m$ ,表示把上一个时刻的数乘上$m$，并输出其对$mod$取模的值

② $2 \;pos$，表示把上一个时刻的数除以第$pos$个时刻乘上的数（保证$pos$时刻执行的1操作），并输出其对$mod$取模的值

数据范围： $Q<=10^5 \; m<=10^9$

【分析与解】

​ 一定要明白删除时怎么被转换的！就是添加的某个东西的作用域被削减了。

​ 所以这道题就是以时间为轴建立线段树，修改对应一个区间，右端点如果有2操作，就是那个时刻-1，否则就是最终时刻。询问就是叶子，然后进行线段树分治即可。

练习三 BZOJ 4025 二分图

【题目描述】

给定一张图$n$个节点$m$条边，每一条边的出现时间为一个区间，问每一段时间是否构成一张二分图。

数据范围：$n<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T $

【分析与解】

二分图有一个重要的性质：

一个图是二分图，当且仅当图中不包含有长度为奇数的环

我们按照时间为轴建立线段树，询问为每一个叶子节点，修改为一段区间。那么对于每一次新加入一条边，我们考虑因为加入了这条边，所造成一个环产生，而这个环是不是奇环。

我们用并查集来维护边的连通性，由于我们要求两个点的链长，所以不能进行路径压缩，只能进行启发式合并。也就是维护两个并查集的$rank$，小的并入大的，然后求链长就是暴力跳到祖先。

由于我们关心链长的奇偶性，所以我们可以在暴力跳的时候每一次异或连向父亲的链的权值，最后两个值异或再异或上1（表示新添加一条链），如果这个值是偶数，那就是合法的，否则是非法的。

对于一个线段树上节点而言，由于是进行完所有修改再询问，如果一旦某一步发生了非法，则整个区间的询问全部是非法。这种情况下就不必再向下递归了。

然后向下递归执行，到叶节点如果没有被判定非法，就是合法的。

但是这里要支持栈序撤销

乍一看要可持久化，其实不然。我们只需要记录两种事件：一种是$rank$数组的变更，一种是父亲的变更。

由于我们在并查集合并时一定是祖先合并，所以撤销也就是$fa[x]=x$，在数组中记录更改的下标即可。对于rank，由于更改就是$+1$，所以只需要记录下标，回溯时-1即可。

如何区分两种操作？只需要令一个是正的，一个是负的（妙）。

复杂度是$O(mlogT)$