[COCI2015-2016#7] Prokletnik
有那么一点点启发性。
假设右端点是最大值，思路很简单很经典，考虑扫描线+线段树，那么修改涉及到的点就是当前的后缀最小值，维护一个单调不减的单调栈，那么单调栈里面的点都要改。
难道我们要遍历单调栈吗？哈哈，并不用，我们直接在单调栈上面建一棵线段树就行了！弹栈的时候就再在第一棵线段树上修改即可！复杂度 \(O(n \log n)\)。
代码失联了qwq...
标签：Prokletnik,COCI2015,一棵,2016,线段,单调 From： https://www.cnblogs.com/DCH233/p/17632568.html