题解：AT_abc428_f [ABC428F] Pyramid Alignment

· · 题解

不用线段树。

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

考虑一个操作 v 会删除所有 \le v 的操作，因此单调栈维护。

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

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

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

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

:::info[note] 具体地，如何维护栈：

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

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

注意 v=n 操作是否会使得维护的奇偶性破坏。 ::: :::warning[ouch] upd：如果栈的大小为 t，可能需要 s_{t+1}\leftarrow0！

我承认写题解的时候其实没过，今天对拍才发现错误然后才过了。