运用时间线段树对树上问题进行离线处理
运用时间线段树对树上问题进行离线处理
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471723
运用时间线段树对树上问题进行离线处理
对于树上问题，有时候离线处理更优，但要维护操作之间的有序性，可以考虑用时间线段树维护。
例题：CF383C
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-25
树套树小结
树套树小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132501426 树状数组套权值线段树，实现过程类似主席树，采用动态开点实现 https://www.luogu.com.cn/problem/P3380 树状数组部分 线段树部分
2023-08-10
颜色类问题与分治：P7215
颜色类问题与分治：P7215 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132221132 https://www.luogu.com.cn/problem/P7215 化为点分治后，把原问题变成钦定一个点必选的问题 转化这一步是点分治维护颜色类题目的一个性质，如果某种颜色外面有，就会在外面被考虑，不需要在此层 对朴素分治也有启发，对于在大区间统计了的答案，就不需要在小区间统计了 考虑在钦定一个点必选时，怎么做，首先把它定义为根。 把每种颜色丢入一个...
2023-08-05
兔队线段树：楼房重建
兔队线段树：楼房重建 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096 https://www.luogu.com.cn/problem/P4198 本质：在线段树上每个节点维护信息时再深入到底部，加个 log\loglog O(nlog2n)O(n\log^2n)O(nlog2n) 总比 O(n2)O(n^2)O(n2) 优。 抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。 合并的过程，显然左子树可以直接继承，所以可以...
2022-04-29
【CF339D Xenia and Bit Operations】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...
2022-01-13
【CF6E Exposition】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15798330.html 题目链接 题目 There are several days left before the fiftieth birthday of a famous Berland's writer Berlbury. In this connection the local library decided to make an exposition of the works of this famous science-ficti...
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...