善用值域数据结构+操作离线：1864F
善用值域数据结构+操作离线：1864F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132631673
发现题目中有两个维度：
-
维护数值，发布计算某种情况下的答案
-
多个查询
两个维度，发现很难分开做。考虑对操作离线，同时维护两个维度的东西。
类似线段操作，左边入时±，右边出时-+
本质是一种扫描线的思想
本博客所有文章除特别声明外，均采用 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]...
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-10-08
ds套DP——考虑位置转移or值域转移：CF1762F
ds套dp——考虑位置转移or值域转移：CF1762F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133691573 https://www.luogu.com.cn/problem/CF1762F 分析性质，就是我们选的数要么递增，要么递减（非严格） 然后很明细是ds套dp， fif_ifi 表示以 iii 开头的答案 然后考虑如何转移（ds套dp难点反而在转移而不是状态，因为要考虑如何和ds结合） 转移的话，要么从位置考虑，要么从值...
2022-01-10
【CF5C Longest Regular Bracket Sequence】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15783397.html 题目链接 题目 This is yet another problem dealing with regular bracket sequences. We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical ex...
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 即可。因为差值更大的我们显然可以最后又会规约成这种情况...