上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果
上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070831
https://www.luogu.com.cn/problem/P8518
没有要求在线，显然离线（。维护时间戳，上线段树。
好了，我们现在知道一个人的曲线变化了。怎么做呢？
前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 即可。因为差值更大的我们显然可以最后又会规约成这种情况。
关于差值的维护，我们维护后缀min/max，然后线段树上二分即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-04-29
【CF339D Xenia and Bit Operations】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...
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 ，朴素思路是用单调队列+区间覆盖维护 那样就不能很方便地维护差 但既然都...
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-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-12-18
离线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即可
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...