上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果

2023-12-18 22:48:11

https://www.luogu.com.cn/problem/P8518

没有要求在线，显然离线（。维护时间戳，上线段树。

好了，我们现在知道一个人的曲线变化了。怎么做呢？

前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 c i c_i ci?即可。因为差值更大的我们显然可以最后又会规约成这种情况。

关于差值的维护，我们维护后缀min/max，然后线段树上二分即可

在这里插入图片描述

文章来源:https://blog.csdn.net/zhangtingxiqwq/article/details/135070831
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。