线段树分治
线段树分治
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126153
https://www.luogu.com.cn/problem/P5787
理解：
-
操作离线
-
用时间线段树维护
-
整体统计答案，进入到某个节点加入，离开时撤销
-
可以用可撤销数据结构维护（可能可以可持久化或LCT维护？以后再学）
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-06
cqd分治思想
cqd分治思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135114 https://www.luogu.com.cn/problem/P3810 常用于维护三维偏序问题，对于相等的情况处理我感觉不太好，之前ABC打cdq被制裁了 三维，第一维显然排序 分治，所以第二维很明显了。因为只需要考虑左对右的贡献，所以黑白染色一下，再按b排即可。然后黑白一个对应查询一个对应修改操作。 最后一个拿树状数组
2023-08-06
线段树合并思想
线段树合并思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135188 直接维护很大，所以每个节点动态开点。 合并时按顺序，一个有一个没直接把有那个连上去。 否则递归。
2022-02-15
【一本通OJ 1603：绿色通道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15897506.html 题目链接 题目 高二数学《绿色通道》总共有 nnn 道题目要抄，编号 1…n1\ldots n1…n，抄第 iii 题要花 aia_iai 分钟。小 Y 决定只用不超过 ttt 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。 现在，小 Y 想知道他在这 ttt 分钟内写哪...
2023-08-24
对于DP颜色类问题的切换方法：P9561
对于dp颜色类问题的切换方法：P9561 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731 对于dp颜色类问题的切换方法 两种颜色为例，一般情况下 dp[i][0]dp[i][0]dp[i][0] 可以由 dp[j][0/1]dp[j][0/1]dp[j][0/1] 在某些情况下转移 但从0到0的过程中，对于 jjj 前的1，可能 jjj 满足，但 iii 不满足 此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我...
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
李超线段树
李超线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217504 插入过程中，先询问中点，让 uuu 在上，它必然覆盖其中一个区间。 然后看看左右端点哪里 vvv 比 uuu 大，就在对应区间递归下去