栈模拟队列学习笔记

这里以窗口长度为 $k$，维护后缀最大值的位置（比 $[j+1,i]$ 中的所有数都大的位置）的 dp 值的最大值为例。

维护底对底的两个单调栈：

两个栈都维护每个元素到栈底之间所有元素的 dp 值的最大值。

后面的栈像普通单调栈一样正常插入删除，前面的栈若栈顶超出了窗口范围则删除栈顶。

若某一个栈空了则重构，把另一个栈的所有元素拿出来，把一半放入原来为空的栈。

这样做的时间复杂度是 $O(n)$ 的，考虑每次重构都是某一边被删空了才会进行，设重构后左边的栈有 $k$ 个元素，则本次重构时间复杂度为 $O(k)$，而若要进行下一次重构，则一定会执行 $O(k)$ 次删除操作，所以重构的时间复杂度和删除的时间复杂度是一样的，均为 $O(n)$。

例题：

• 【2023成都集训模拟赛04】op

双指针移动过程中，修改操作直接进行（在操作栈顶压入操作）。对于删除操作，则暴力弹栈（撤销）并将弹出的操作暂存到一个数组 $b$ 中，直到栈顶为想要删除的操作。此时弹栈，然后再弹出栈顶 $|b|$ 个元素（不足 $|b|$ 个则弹空），并将这些元素也加入 $b$。最后将 $b$ 中元素按照编号排序，再从大到小依次压入栈中。

考虑每个时刻栈底到栈顶都形如若干段下降段。

由于每次删除的是最小值，故执行删除操作时，一个下降段要么被完全跳过，要么被删掉靠近栈顶的第一个元素。而一个下降段若被完全跳过，则其会在排序中和其它下降段融合，故其长度至少翻倍，故这部分的时间复杂度是 $O(n\log n)$ 的；而删除靠近栈顶的第一个元素这个操作只会进行总共 $n$ 次，故这部分的时间复杂度是 $O(n)$ 的。

所以总复杂度是 $O(n\log n)$，算上排序和可撤销数据结构的复杂度即为 $O(n\log ^2n+n\log nM)$，其中假定可撤销数据结构的单次操作（修改、撤销）的复杂度为 $O(M)$。

int top,sta[S],b[S];
inline void push(int x)
{
	work(x);
	sta[++top]=x;
}
inline void pop(int x)
{
	int cnt=0;
	while(sta[top]!=x) undo(),b[++cnt]=sta[top--];
	undo(),top--;
	for(int i=1,len=cnt;i<=len&&top>0;i++) undo(),b[++cnt]=sta[top--];
	sort(b+1,b+cnt+1);
	for(int i=cnt;i>=1;i--) work(b[i]),sta[++top]=b[i];
}