题意简述

有$n$个栈，编号为$1$到$n$。有$m$个操作，如下三种：

1 l r : 计算第$l$到第$r$个栈的栈顶元素之和。

2 l : 第$l$个栈弹出栈顶元素，如果不存在则不执行。

3 l r x : 第$l$到第$r$个栈都把$x$压栈。

强制在线。

$1 \le n, m \le 5 \times 10 ^ 5, 1 \le x \le 10 ^ 3$

算法讨论

一开始一直在想是不是要线段树上弄一些奇形怪状的标记。

看过标算感觉有点神，而且挺小清新的。

考虑栈的性质。退栈就相当与撤销修改操作嘛。

考虑建立可持久化线段树，维护每个位置最近的修改时间和栈顶的权值。

那么区间压栈就相当于区间覆盖。注意，可持久化线段树上区间覆盖较难下传标记，考虑到只有单点查询，标记永久化即可。单点弹栈的话我们可以去找到最近的修改时间-1的时间点查询到上次修改的信息，并直接拿过来覆盖到这个时间点上就相当于我们撤销了一次修改。

对于询问，我们可以另建一棵普通线段树，上面维护所有位置的栈顶元素。维护时一起修改一下就好了。

时间复杂度和空间复杂度均为$O(n \log n)$，空间的常数有点大。