[HDU5818]Joint Stacks(可并堆,左偏树)

发布于 2018-02-18  215 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5818]Joint Stacks(可并堆,左偏树)

Description

A stack is a data structure in which all insertions and deletions of entries are made at one end, called the "top" of the stack. The last entry which is inserted is the first one that will be removed. In another word, the operations perform in a Last-In-First-Out (LIFO) manner.
A mergeable stack is a stack with "merge" operation. There are three kinds of operation as follows:
- push A x: insert x into stack A
- pop A: remove the top element of stack A
- merge A B: merge stack A and B

After an operation "merge A B", stack A will obtain all elements that A and B contained before, and B will become empty. The elements in the new stack are rearranged according to the time when they were pushed, just like repeating their "push" operations in one stack. See the sample input/output for further explanation.
Given two mergeable stacks A and B, implement operations mentioned above.

Http

HDU

Tag

可并堆,左偏树

题目大意

维护一个“可并栈”,要求支持弹入、弹出和合并的操作,合并两个栈后,新栈的元素排列按照原来两个栈中的时间戳从大往小排列。

解决思路

看到合并两个栈的方式,发现就是按照时间戳排序,直接用可并堆维护即可,堆中用于比较大小的是时间戳。
这里使用左偏树实现可并堆。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5818]Joint Stacks(可并堆,左偏树)


HNCJ OIer