526互联

[COCI2015-2016#7] Prokletnik

发布时间 2023-08-15 21:58:42作者: DCH233

[COCI2015-2016#7] Prokletnik

有那么一点点启发性。

假设右端点是最大值，思路很简单很经典，考虑扫描线+线段树，那么修改涉及到的点就是当前的后缀最小值，维护一个单调不减的单调栈，那么单调栈里面的点都要改。

难道我们要遍历单调栈吗？哈哈，并不用，我们直接在单调栈上面建一棵线段树就行了！弹栈的时候就再在第一棵线段树上修改即可！复杂度 \(O(n \log n)\)。

代码失联了qwq...