题面:http://uoj.ac/contest/32/problem/218
题意
有$n$个栈,区间压数,单点弹栈,求区间栈顶和。
线段树
看到此类区间修改,区间询问的题目,我们很容易想到线段树这样的数据结构。
我们可以通过对线段树打标记来实现区间修改。在访问线段树的每个结点时,我们还需要进行标记下传。
这种做法要求标记能快速合并,并且有结合律。
标记
这题的修改操作为“区间压数”,即对区间的每个栈压一个数进去。
所以我们可以考虑用一个序列来表示标记,该标记的意思为对于这个线段树区间里的每个栈,都要将这个序列按顺序压进去。
于是合并两个标记的时候就只要将这两个序列连接(join)。
在区间压数操作中,我们找到对应的区间后,给该区间打上一个只有一个元素的序列的标记。
在单点弹栈操作中,我们将跟该点有关的标记全部下传之后,需要将该点的标记里的序列中第一个数删掉(即“弹栈”),并更新该点的答案。
由于有询问区间和的操作,我们在线段树上还需要维护区间和,只要在标记下传的时候维护即可。
“序列”
除了需要维护一个“序列”以外,线段树上所有操作的复杂度都是$O(\log n)$的。
这个序列需要支持:
- 生成一个只有一个元素的序列;
- 将两个序列连接;
- 删除某个序列的第一个元素。
以上操作都要求完全可持久化。
在一次题目的操作中,会有至多$\lceil 2 \log n \rceil$次序列连接操作,和至多一次生成序列或者删除第一个元素的操作。
平衡树
我们可以使用可持久化平衡树(如AVL或treap)来维护这些序列,复杂度为严格或期望$O(\log n)$单次序列操作。
这样题目中每次操作的复杂度为$O(\log ^ 2 n)$,并不是很优美,而且平衡树常数很大,代码也很难写……
二叉树
我们可以用一种不知名的二叉树来维护这个序列。
对于一个长度为$k$的序列,对应的二叉树上有$2k-1$个结点,其中根节点的值为该序列的第一个元素的值。
我们可以这样递归定义这种二叉树以及其连接操作:
- 基础:$k = 1$时,二叉树上只有一个结点,该结点的值为序列中唯一一个元素的值。
- 归纳:将两个长度分别为$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)$。