线段树分治
标签(空格分隔): 数据结构 线段树分治 笔记
概述
思想
线段树分治是基于时间的划分, 可以维护删除操作
具体方法是将一个操作的存在时间划分为 \(O(\log n)\)个子段将删除操作改为撤销操作
问题类型
解决的范围很窄, 基本上是下面两个特性就可以选择
离线
易加难减
套路
将操作存在的时间取出
建立线段树, 并在每一个操作对应的存在区间打上相应的标记
递归地加入操作和撤销操作, 并 \(dfs\)一次线段树统计答案
基本上对于每道题个性化的部分就是怎么实现撤销功能
例题
\(\mathtt{BSOJ5888}\):
维护一个数 \(x\pmod M\)意义下的值, 支持乘上一个数, 除以一个之前乘过的数 (\(M\) 不一定为质数)
用这道题说明一下怎么分治转除掉一个数为撤销乘上这个数
首先我们可以轻易维护出每个乘数 \(m\)存在的时间 \([l,r]\)(真实情况是第 \(l\)时刻乘, 第 \(r+1\)个时刻除掉), 考虑在树状数组上对每个 \(m\)对应作用区间打永久化标记 \([l,r]\), 最后一次 \(dfs\)统计答案即可
这道题实际上是用标记永久化来实现撤销
其实这个撤销的意思说起来难也很简单
伪代码:
Solve(x){
统计(用 Ans 去更新答案, Ans 可能发生改变)
Solve(rs),Solve(ls)
复原 Ans
}
复原一个值很轻松, 但如果是一个数据结构, 那我们就要强行可撤销化
介绍一下套路, 用一个栈按照顺序记录操作更改的量
比如对可撤销并查集 (\(top\) 隐性表示操作顺序(相对))
\(++top,size[y]+=size[x],fa[x]=y\)就记下 \(\{top,x,y\}\)这三个量
退栈时就 \(--top,size[y]-=size[x],fa[x]=x\)
有更多的改变量也是同理
\(\mathtt{BSOJ5219}\):
可离线前提下支持
加删边 \((x,y)\)
查询两点连通性
\(\mathtt{BSOJ5399}\): 线段树分治 + 可撤销带权并查集, 很裸
\(\mathtt{BSOJ1685}\): 线段树分治 + 线性基(你可以发现线性基就是常数个量, 不用可撤销)
\(\mathtt{BSOJ5890}\): 线段树分治 + 可撤销可持久化 \(trie\)树
来源: http://www.bubuko.com/infodetail-3453239.html