树套树小结
树套树小结
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132501426
树状数组套权值线段树，实现过程类似主席树，采用动态开点实现
https://www.luogu.com.cn/problem/P3380
树状数组部分
线段树部分
本博客所有文章除特别声明外，均采用 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...
2022-02-16
【一本通OJ 1600：【例 4】旅行问题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接 题目 原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为...
2023-08-10
点分治过程中维护李超线段树：CF1303G
点分治过程中维护李超线段树：CF1303G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132219909 https://www.luogu.com.cn/problem/CF1303G 看到这题，首先很容易想到树形dp，但发现要维护两个值，一个为末项，一个为和，很好分析出这个东西有凸性。 这个时候有两种做法，维护凸包或李超线段树。 之所以用李超线段树，是可以想象出维护末项（k）和和 （b）之后最终的答案其实之和队对面的深度（x）有关，而这个大胆猜测可以...
2023-08-24
运用时间线段树对树上问题进行离线处理
运用时间线段树对树上问题进行离线处理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471723 运用时间线段树对树上问题进行离线处理 对于树上问题，有时候离线处理更优，但要维护操作之间的有序性，可以考虑用时间线段树维护。 例题：CF383C
2023-08-10
点分治小结
点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...
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∈...