题解：AT_abc428_f [ABC428F] Pyramid Alignment

不用线段树。

首先发现两个区间必定是包含关系。不难想到二分。

考虑一个操作

v

会删除所有

\le v

的操作，因此单调栈维护。

以栈内元素把区间分段，先二分属于哪段，再二分在该段内的位置。

考虑二分第一个。需要维护栈内区间左端点。

（具体地，考虑栈插入时左端点从上一个元素转移，加上一次对齐的偏移量，类似前缀和。）

考虑二分第二个。这些区间与对应的栈内元素对齐，简单推下此时区间的左右端点即可。

note

具体地，如何维护栈：

插入元素并删除完之后，如果剩下的操作种类和当前一样，显然忽略当前操作。

此时，相邻元素的操作种类不同。可以考虑偶下标维护

l

操作。

注意

v=n

操作是否会使得维护的奇偶性破坏。

文章操作