线段树分治
线段树分治通过将操作离线,并增加 \(O(\log m)\) 的时间复杂度,使得既有插入又有删除的问题转化为只有插入和撤销的子问题。
某些数据结构容易实现插入操作,但是不易或无法实现删除操作。使用线段树分治就可以将删除操作转化为撤销操作,用栈存储数组的变化即可。
使用线段树分治需要满足以下条件:
- 题目中有插入和删除两种操作;
- 数据结构容易实现插入,但不易实现删除;
- 数据结构是非均摊的,因此撤销的时间复杂度有保障。
我们先对每一个元素求出其出现的时间 \([l,r]\),即该元素在 \(l\) 时刻插入,\(r+1\) 时刻删除。我们在 \(T+1\) 时刻将所有未删除的元素全部删除,保证 \(r\) 有效。
然后将 \([l,r]\) 拍到线段树上,分解为 \(O(m\log m)\) 个区间,将元素的信息添加到对应的区间上。线段树的性质保证这些区间要么包含要么无交。
接着,对线段树进行 dfs
,每遍历到一个节点(区间),就将该节点记录的所有元素都插入到数据结构中,然后向子节点递归。如果当前已经是叶子节点,则直接在数据结构上进行查询即可。子节点递归结束后,撤销该节点产生的所有插入操作。
正确性显然:当位于叶节点 \([l,l]\) 时,只有包含 \(l\) 的区间才有贡献。
P5787 二分图 /【模板】线段树分治
题意
有加边和删边两种操作,你需要在每次操作后判定原图是不是二分图。
动态判定二分图可以使用并查集(带权或扩展域)解决。但是并查集只能维护加边的操作,而无法删除其中的某条边。
考虑线段树分治。我们只需要使用启发式合并的并查集,即可实现非均摊 \(O(\log n)\) 合并,用栈维护即可。
模板代码
P3733 [HAOI2017] 八纵八横
题意
给定一个无向连通图 \(G=(V,E)\),边有边权。定义一个环(不要求为简单环)的权值为边权异或和。
有两种操作:
- 向图中加入一条边;
- 删除一条以前加入的边(不会删除初始图中的边);
要求你在每次操作结束后,输出所有环的权值的最大值。
我们随便选择初始图 \(G\) 的一棵生成树,对于每一条非树边,它都能和树边形成一个环,这样的环称为基本环。能够证明,任意环都可以被表示为一些基本环的异或。
因此,我们只需要使用线性基维护所有基本环,就可以快速查询答案。
然而,普通的线性基无法实现删除操作。又因为没有强制在线,因此考虑线段树分治,将删除操作变为撤销操作。
线性基不是均摊的,因此我们只需要用栈记录数组的变化,即可实现撤销操作。
代码
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
|
P9168 [省选联考 2023] 人员调度
题意
有一棵 \(n\) 个节点的有根树,根节点是 \(1\) 号节点。每个节点对应一个可重集 \(S_i\)。你可以进行若干次操作,每次操作你可以选定一个节点 \(u\) 和 \(S_u\) 中的一个元素 \(x\),然后选定一个 \(u\) 子树内的节点 \(v\),将 \(x\) 从 \(S_u\) 移动到 \(S_v\) 中。最终,你会获得 \(\sum_{u}\max\{S_u\}\) 的价值。
初始时所有可重集为空,你需要维护两种操作,并在每次操作之后输出能够得到的最大价值:
- 向 \(S_u\) 加入一个元素 \(x\);
- 从 \(S_u\) 中删除一个 \(x\),保证 \(x\in S_u\);
\(n,m\le 10^5\)
静态问题和简化模型
考虑静态问题怎么做。假设 \(u\) 的所有儿子子树的内部已经分配完成,考虑挂在 \(u\) 节点上的员工:如果儿子子树内存在空位,那么 \(u\) 会优先填充这些空位;没有空位之后,\(u\) 会选择子树中最劣的一个位置踢掉,然后自己加进去。
考虑如何进一步刻画这个过程。我们可以将子树内产生贡献的员工从大到小排成一个序列,如果子树内有空位,那么序列的长度小于子树大小之和;否则取等。对于 \(u\) 节点,依照上面的过程我们会先尝试用 \(u\) 节点本身的员工将序列长度补充到 \(sz[u]\);然后,我们会剔除序列末尾更劣的一个后缀,并加入 \(u\) 的部分员工。
这个过程可以看作是将各个子树的序列依次拼接,然后再把 \(u\) 的员工也加入序列,最后从小到大排序,保留前 \(sz[u]\) 个元素。
动态维护
先考虑只有插入操作怎么做。我们关心新加的员工是否会产生贡献,并且是否会替换其他的员工。注意到,在序列中被删除的员工,以后也不可能产生贡献,因此自动将他们删除,不会改变答案。
如果插入时,\(u\) 的根链的序列都没有溢出,那么 \(u\) 将会直接插入。否则,在第一个溢出的位置 \(t\),\(u\) 要么替换掉最劣的一个人,自己保留到根,要么直接被干掉,不产生贡献。而那些原本就已经被淘汰的员工,如果他们有实力淘汰 \(u\),那么 \(u\) 也一定不能在 \(t\) 处存活下来;而且上面也分析过,直接删除它们不会影响答案。
我们需要动态查询根链上第一个满的位置,并且支持链加;还要查询子树内的最小值。使用树剖和线段树维护即可。
带删除
对于删除操作,发现操作都是非均摊的,线段树分治即可。
时间复杂度 \(O(q\log^2 n\log q)\)。
代码
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 |
|