HDU 5818 Joint Stacks（左偏树）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5818
【题目大意】
给出两个栈A B(初始时为空)，有三种操作： push、pop、merge. 其中merge是按照A B中元素进栈的相对顺序来重排的.
【题解】
我们在当A，B栈出现第一个元素时，我们以这个元素建立左偏树，将其root赋值给所属栈，对于插入和输出堆顶操作，我们直接利用左偏树的功能实现，至于A,B的合并，我们将两棵左偏树合并后将一个标志置空即可。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <cstdio>#include <algorithm>#include <utility>using namespace std;int n,A,B,x;char op[10],c[10];const int N=1000005; typedef pair<int,int>P;struct Node{ int l,r,d;P v; Node(){} Node(int _l,int _r,int _d,P _v){l=_l,r=_r,d=_d,v=_v;}}T[N];int merge(int a,int b){ if(!a)return b; if(!b)return a; if(T[a].v<T[b].v)swap(a,b); T[a].r=merge(T[a].r,b); if(T[T[a].l].d<T[T[a].r].d)swap(T[a].l,T[a].r); T[a].d=T[a].r?T[T[a].r].d+1:0; return a;}int pop(int a){ int l=T[a].l,r=T[a].r; T[a].l=T[a].r=T[a].d=0; return merge(l,r);}int Cas=1;int main(){ while(~scanf("%d",&n),n){ printf("Case #%d:\n",Cas++); A=B=0; for(int i=1;i<=n;i++){ scanf(" %s %s",op,c); if(op[0]=='m'){ if(c[0]=='A'){ scanf(" %s",c); if(A==0)A=B,B=0; else if(B==0)continue; else A=merge(A,B),B=0; }else{ scanf(" %s",c); if(B==0)B=A,A=0; else if(A==0)continue; else B=merge(A,B),A=0; } }else{ if(op[1]=='o'){ if(c[0]=='A'){ if(A==0)continue; printf("%d\n",T[A].v.second); A=pop(A); }else{ if(B==0)continue; printf("%d\n",T[B].v.second); B=pop(B); } }else{ scanf("%d",&x); T[i]=Node(0,0,0,{i,x}); if(c[0]=='A'){ if(A==0)A=i; else A=merge(A,i); }else{ if(B==0)B=i; else B=merge(B,i); } } } } }return 0;} |
评论 (0)
