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

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


本文章由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

可并堆,左偏树

题目大意

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

解决思路

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

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101000;
const int inf=2147483647;

class Heap
{
public:
    int key,wth;//值,时间戳
    int ls,rs,dis;
    void init(){
            ls=rs=dis=0;return;
        }
};

int n;
Heap H[maxN];

int Merge(int r1,int r2);

int main()
{
    int cas=0;
    ios::sync_with_stdio(false);
    while (scanf("%d",&n))
    {
        if (n==0) break;
        printf("Case #%d:\n",++cas);
        int rt[3],nodecnt=0,tim=0;
        rt[1]=rt[2]=0;//初始化
        char opt[20];
        while (n--)
        {
            cin>>opt;
            if ((opt[0]=='p')&&(opt[1]=='u'))//加入一个元素
            {
                char hp;int key;cin>>hp>>key;hp=hp-'A'+1;
                tim++;nodecnt++;
                H[nodecnt].init();
                H[nodecnt].key=key;H[nodecnt].wth=tim;
                rt[hp]=Merge(rt[hp],nodecnt);
            }
            if ((opt[0]=='p')&&(opt[1]=='o'))//弹出
            {
                char hp;cin>>hp;hp=hp-'A'+1;
                printf("%d\n",H[rt[hp]].key);
                rt[hp]=Merge(H[rt[hp]].ls,H[rt[hp]].rs);
            }
            if (opt[0]=='m')//合并
            {
                char hp1,hp2;cin>>hp1>>hp2;
                hp1=hp1-'A'+1;hp2=hp2-'A'+1;
                rt[hp1]=Merge(rt[hp1],rt[hp2]);
                rt[hp2]=0;
            }
        }
    }
    return 0;
}

int Merge(int r1,int r2)
{
    if (r1==0) return r2;
    if (r2==0) return r1;
    if (H[r1].wth<H[r2].wth) swap(r1,r2);
    H[r1].rs=Merge(H[r1].rs,r2);
    if (H[H[r1].ls].dis<H[H[r1].rs].dis) swap(H[r1].ls,H[r1].rs);
    if (H[r1].rs) H[r1].dis=H[H[r1].rs].dis+1;
    else H[r1].dis=0;
    return r1;
}

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

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


HNCJ OIer