（非颜色、包含）线段类问题——离线+扫描线+DS：0926T4
（非颜色、包含）线段类问题——离线+扫描线+DS：0926T4
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133309861
这种类型的题其实很单一
首先有一堆线段，有询问，直接离线，然后上扫描线，然后套DS
问题来了，ds维护什么？
此题询问的看似是单点问题，本质是区间问题。
我们要尝试对题目进行转换，如果整个区间所有都满足，则单点必然满足
回到此题。首先扫描线满足了右端点。
那么ds只能维护左端点了。
既然是维护端点值，那么只能维护最值。
维护最值的话，维护最小值没啥大意义，那就只能维护最大值。
维护最大值的话，只要满足这个区间内覆盖此点的左端点都在询问区间的左端点之前，那么就此询问必然可以。
而在这个过程中，我们成功把复杂的单点问题转化为简单的区间问题。之间SegmentTree即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-21
数据结构中的判定转状态+扫描线：P1502
数据结构中的判定转状态+扫描线：P1502 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133124669 https://www.luogu.com.cn/problem/P1502 发现正常扫描线很难维护恰好大小为 WWW 的区间 反过来，对于每个星星维护合法的左下角下标 把原先的判定转成了和点有关的状态，把点变成矩形后求并即可 12345678910111213141516171819202122232425262728293031323334353...
2023-11-06
珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3
珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134249552 http://cplusoj.com/d/senior/p/SS231031C 珂朵莉树有个很好的性质： 任意时刻，所有区间都是不交的 所以我们可以把所有区间先拿珂朵莉树变成一堆小区间，每个区间有个存活时间 [t1,t2][t_1,t_2][t1,t2] 考虑这个区间意义。他会在 l∈[1,t1],r∈[t1,t2]...
2023-12-18
上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果
上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070831 https://www.luogu.com.cn/problem/P8518 没有要求在线，显然离线（。维护时间戳，上线段树。 好了，我们现在知道一个人的曲线变化了。怎么做呢？ 前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 cic_ici 即可。因为差值更大的我们显然可以最后又会规约成这种情况...
2023-09-11
离线建AC自动机维护子串+线段树维护AC自动机：HDU4117
离线建AC自动机维护子串+线段树维护AC自动机：HDU4117 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132804430 https://acm.hdu.edu.cn/showproblem.php?pid=4117 离线处理 AC自动机每次插入都要重构，但其实可以先离线建好，再进行操作 AC自动机理解——维护子串 每个子串都可以表示成一个前缀的一个后缀。 任意一个前缀是Trie树上的一个点，然后其对应后缀就是fail树上的祖先 fail树本质是一个...
2023-10-24
线段树维护势能类 / 均摊类问题：CF403E
线段树维护势能类 / 均摊类问题：CF403E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134002988 https://www.luogu.com.cn/problem/CF403E 场上想对于一棵树的某个子树把所有向外边全部删掉 变成dfn序一个在子树区间，一个不在的问题 易发现这个问题可以用线段树维护 在一个点在其dfn序加入另一个点，维护区间另一个点dfn序的最大和最小值 如果不在询问区间里，直接递归 易证明均摊是 O(nlogn)O(n...
2023-10-10
注意分类讨论完整性：CF1371F
注意分类讨论完整性：CF1371F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133745577 https://www.luogu.com.cn/problem/CF1371F 此题要分类讨论完全 容易漏掉 >>>>><<<<< 在左右或中间的情况 多对拍 123456789101112131415161718192021222324252627282930313233343536373839...