题面：http://uoj.ac/contest/32/problem/218

题意

有$n$个栈，区间压数，单点弹栈，求区间栈顶和。

线段树

看到此类区间修改，区间询问的题目，我们很容易想到线段树这样的数据结构。

我们可以通过对线段树打标记来实现区间修改。在访问线段树的每个结点时，我们还需要进行标记下传。

这种做法要求标记能快速合并，并且有结合律。

标记

这题的修改操作为“区间压数”，即对区间的每个栈压一个数进去。 所以我们可以考虑用一个序列来表示标记，该标记的意思为对于这个线段树区间里的每个栈，都要将这个序列按顺序压进去。 于是合并两个标记的时候就只要将这两个序列连接(join)。

在区间压数操作中，我们找到对应的区间后，给该区间打上一个只有一个元素的序列的标记。

在单点弹栈操作中，我们将跟该点有关的标记全部下传之后，需要将该点的标记里的序列中第一个数删掉（即“弹栈”），并更新该点的答案。

由于有询问区间和的操作，我们在线段树上还需要维护区间和，只要在标记下传的时候维护即可。

“序列”

除了需要维护一个“序列”以外，线段树上所有操作的复杂度都是$O(\log n)$的。

这个序列需要支持：

1. 生成一个只有一个元素的序列；
2. 将两个序列连接；
3. 删除某个序列的第一个元素。

以上操作都要求完全可持久化。

在一次题目的操作中，会有至多$\lceil 2 \log n \rceil$次序列连接操作，和至多一次生成序列或者删除第一个元素的操作。

平衡树

我们可以使用可持久化平衡树（如AVL或treap）来维护这些序列，复杂度为严格或期望$O(\log n)$单次序列操作。

这样题目中每次操作的复杂度为$O(\log ^ 2 n)$，并不是很优美，而且平衡树常数很大，代码也很难写……

二叉树

我们可以用一种不知名的二叉树来维护这个序列。

对于一个长度为$k$的序列，对应的二叉树上有$2k-1$个结点，其中根节点的值为该序列的第一个元素的值。

我们可以这样递归定义这种二叉树以及其连接操作：

1. 基础：$k = 1$时，二叉树上只有一个结点，该结点的值为序列中唯一一个元素的值。
2. 归纳：将两个长度分别为$n$和$m$的序列$a$和$b$连接起来时，我们新建一个结点，该结点的值为$a$中第一个元素的值（即，$a$对应二叉树的根节点的值），左儿子和右儿子分别为$a$和$b$对应二叉树的根节点。

可以证明这样构造的二叉树满足其定义。

在序列中删除第一个元素的时候，我们从根开始，一直向左走直到叶结点，则这个叶结点一定表示序列中第一个元素。

我们将这个叶结点的父结点替换为这个叶结点的父结点的右儿子，并更新父结点到根路径上的每个结点的值。

对于该叶结点没有父结点的情况，说明是只有一个元素的序列，直接返回空树即可。

复杂度分析：

生成序列、序列连接都是$O(1)$的，删除第一个元素是$O(表示序列中第一个元素的结点的深度)$的。

注意到在线段树上，打标记会使该深度变为1或2，每次标记下传会使该深度加一。

由于线段树的深度不超过$\lceil \log n \rceil$，所以该深度不会超过$\lceil \log n \rceil + 1$。

另外注意到每个元素的深度可以单独分析，于是在删除了第一个元素后，第二个元素的深度也满足上述条件。

所以删除第一个元素的复杂度为$O(\log n)$。

综上，这个做法在题目中单次操作的复杂度为$O(\log n)$，可以AC此题。

总结

用带标记的线段树这一经典数据结构和二叉树的有关知识，给出了一个简单的算法， 然后通过观察线段树标记下传的性质，证明该算法的复杂度为每次操作$O(\log n)$。