离线ODT线段树 + 二分双指针：CF1034D
离线ODT线段树 + 二分双指针：CF1034D
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135071061
https://www.luogu.com.cn/problem/CF1034D
多组询问查询区间并是好做的，经典套路：离线+ODT+线段树
考虑这道题，显然二分一下， 然后我们暴力跑ODT和线段树的过程， 每次在线段树上二分即可（当然也可以建主席树），复杂度双log，听说过不了
但是显然具有单调性吧，所以two-pointers即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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-10-18
set维护连续段+线段树：1018T2
set维护连续段+线段树：1018T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133914164 http://cplusoj.com/d/senior/p/386?tid=652f5fe6c1fe41bc229c18fb 线段树维护01，和，支持翻转操作 用类似珂朵莉树的方法维护连续段，连续段之间分别统计，取max 1234567891011121314151617181920212223242526272829303132333435363738...
2023-09-21
数据结构中的判定转状态+扫描线：P1502
数据结构中的判定转状态+扫描线：P1502 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133124669 https://www.luogu.com.cn/problem/P1502 发现正常扫描线很难维护恰好大小为 WWW 的区间 反过来，对于每个星星维护合法的左下角下标 把原先的判定转成了和点有关的状态，把点变成矩形后求并即可 12345678910111213141516171819202122232425262728293031323334353...
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
式子表达ds类——多用位置/值域表示未知数+区间覆盖转区间加：CF407E
式子表达ds类——多用位置/值域表示未知数+区间覆盖转区间加：CF407E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133749252 https://www.luogu.com.cn/problem/CF407E 多用位置/值域表示未知数 推出的式子中 nnn 表示长度，应该直接换成 r−l+1r-l+1r−l+1 区间覆盖转区间加 推出的式子有 mx,mnmx,mnmx,mn ，朴素思路是用单调队列+区间覆盖维护 那样就不能很方便地维护差 但既然都...
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 分钟内写哪...