A simple Blog for wyx I've been down the bottle hoping.
UOJ #218 火车管理 树套树 线段树 数据结构的新思路
发表于: | 分类: Oi | 评论:0 | 阅读:69

啦啦啦~我是来送题解的,在胡策的时候很遗憾没人A这题,不过大家的思路还是非常之妙的,现在我总结一番~

题目大意 :维护$n$个可持久化的栈,要求支持
1.区间压入一个数
2.单点弹出一个数
3.区间栈顶元素求和

思路一 线段树+主席树

我们可以利用线段树+主席树来解决这道题
在主席树上我们存一下每个点的入栈时间,那么显然在他入栈的前一个时刻该位置的元素就是栈顶的下面一个。
那么我们就可以支持弹栈的时候找到上一个元素是谁
于是我们在主席树上维护刚才说的那个东西,然后在一颗正常的线段树上正常的维护区间信息就行了
于是三个操作分别对应着
1.线段树区间覆盖+主席树区间更新
2.主席树单点查询+单点修改(只需要直接把当前时刻的栈顶信息全都改成之前的就行了)+线段树单点修改
3.线段树的区间求和

可能这个时候你会思考为啥不在主席树上直接维护一下和之类的信息。不维护的原因是主席树的空间要求过大,加上区间更新的主席树常数和空间双双飞起,加上UOJ一向强势的数据,很容易MLE,其实这样的构造方法很简单,你只需要吧左端点放在前一半,右端点固定是$n$就能卡掉一批复杂度不正确的做法
所以我们直接单开出$n \log n$的空间维护一下就行了
另外简单说下主席树的区间修改。和正常的线段树一样我们也可以打标记,但是在$down$的时候我们要新开两个一样的儿子,更改儿子的指向,然后再先传标记才行。

树套树

单点查询非常有意味
单点说明我们可以进行标记永久化。这样线段树维护的就只是标记了,查询也只需要遍历包括他的每个区间的标记就行了
用什么维护标记呢?他需要支持区间的分裂,嗯!我们可以利用$fhq\quad treap$
由于使用了可持久化的$treap$,复杂度啥的都特别稳定,是两个$log$乘在一起。
每次的弹栈对应的其实就是$treap$的$split$操作了

树套堆

难道只能用带有可持久化的性质的数据结构解决问题么?我们可以自己造一个适应这题的可持久化数据结构。考虑这样一个事情,栈顶元素的入栈时间在整个栈中一定是最大的!我们可以利用这个性质解决问题。
我们依然使用可持久化来解决区间覆盖单点查询的问题,然而标记用什么维护呢?我们要求查询最大值,所以那个堆维护一下运行了~这样的话每次的查询就从根走到该点,将路径上的堆的对顶的最大值记录下来(按时间序),然后取出这个堆顶,并更新一下线段树的区间和就行了。但是要注意一个问题,比如我在$[l,r]$这段区间取出了他的堆顶元素更新了一波,假设是$pos$这个位置,那么我还需要把这个标记丢到$[l,pos-1],[pos+1,r]$区间里面去
这个和刚才栈全体扔一个数进去是一样的。

一些代码实现

我并没找到有关算法二的代码,可能是数据太强被卡常数了吧
算法一-infinity37
算法一-szy
算法三-mine

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP