兔队线段树：楼房重建
兔队线段树：楼房重建
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096
https://www.luogu.com.cn/problem/P4198
本质：在线段树上每个节点维护信息时再深入到底部，加个
总比 优。
抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。
合并的过程，显然左子树可以直接继承，所以可以写个merge计算右子树在存在左子树情况下的贡献。
对于右子树，显然可以分类讨论，必然会递归到其左子树或右子树之一，而另一个可以直接算。
（侵删）
之前好像做过一道运用此思想的题目，看时候能找到，到时候写一下。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-18
【P2344 [USACO11FEB]Generic Cow Protests G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。 可是这样的时间复杂度为 O...
2023-08-12
线段树记录系数维护动态信息：ZR2612
线段树记录系数维护动态信息：ZR2612 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132255084 http://zhengruioi.com/problem/2612 ai+bj≥0a_i+b_j\ge 0ai+bj≥0 => ai≥−bja_i\ge -b_jai≥−bj 因此考虑把 bbb 去负， ai≥bja_i\ge b_jai≥bj 也就是一个区间 aaa 最小值大于 bbb 最大值 套路1 （大小关系转不同） 对于此...
2023-08-08
zkw线段树
zkw线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132177887 启蒙题： http://zhengruioi.com/problem/2609 参考论文： https://wenku.baidu.com/view/f27db60ee87101f69e319544.html?wkts=1691491614153 不用递归，通过位运算实现的线段树。（本质：线段树为一颗满二叉树） 如果值域为 VVV ，那么zkw只能维护到 V−2V-2V−2 的值...
2022-02-16
【一本通OJ 1600：【例 4】旅行问题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接 题目 原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为...
2023-08-08
通过数据结构维护数论分块结果：ZR2609
通过数据结构维护数论分块结果：ZR2609 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132178041 http://zhengruioi.com/problem/2609 对于 这类东西，应该是自然反应，枚举个 aia_iai ，然后数论分块，这里是 O(nn)O(n\sqrt n)O(nn) 然后会在纸上推一大轮（结论忘了）推出 xxx 的合法区间 [l,r][l,r][l,r] ，然后就是判断 aj∈[l,r]a_j\in[l,r]aj∈...
2023-08-10
颜色类问题与分治：P7215
颜色类问题与分治：P7215 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132221132 https://www.luogu.com.cn/problem/P7215 化为点分治后，把原问题变成钦定一个点必选的问题 转化这一步是点分治维护颜色类题目的一个性质，如果某种颜色外面有，就会在外面被考虑，不需要在此层 对朴素分治也有启发，对于在大区间统计了的答案，就不需要在小区间统计了 考虑在钦定一个点必选时，怎么做，首先把它定义为根。 把每种颜色丢入一个...