AC. 梦想

frank_c1

[UOJ 218] 火车管理

发布于2017年04月14日 | 暂无评论 | 307阅读 | 主席树,可持久化

题意简述

n个栈,编号为1n。有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),空间的常数有点大。