这题合并栈让我们想到了左偏树。
我们可以维护val值为时间，dis值为size的左偏树，定义两个根root1和root2，表示两个栈的栈顶，建大根的左偏树。
接下来的插入，删除，两个栈合并都是左偏树的基本操作，直接写即可，代码里有注释。
#include<bits/stdc++.h>
#define maxn 100001
#define inf 0x7f7f7f7f
using namespace std;
int sum[maxn],ch[maxn][2],dis[maxn],root1,root2,n,tot,cnt,val[maxn],x,y;
char ch2[10],ch1[10];
int merge(int x,int y)
{
if(!x||!y)
{
return x+y;
}
if(val[x]<val[y])
{
swap(x,y);
}
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]])
{
swap(ch[x][0],ch[x][1]);
}
dis[x]=dis[ch[x][1]]+1;
return x;
}
void pop(int &x)//删除
{
x=merge(ch[x][0],ch[x][1]);
}
int main()
{
while(scanf("%d",&n)&&n)
{
printf("Case #%d:\n",++tot);
cnt=root1=root2=0;
memset(ch,0,sizeof(ch));
for(int i=1;i<=n;i++)
{
scanf("%s",ch2);
if(ch2[1]=='u') //添加一个值
{
scanf("%s%d",ch2,&x);
val[++cnt]=i;
sum[cnt]=x;
dis[cnt]=1;
if(ch2[0]=='A')
{
root1=merge(root1,cnt);
}else{
root2=merge(root2,cnt);
}
} else {
if(ch2[1]=='o') //查询
{
scanf("%s",ch2);
if(ch2[0]=='A')
{
printf("%d\n",sum[root1]);
pop(root1);
}else{
printf("%d\n",sum[root2]);
pop(root2);
}
}else{
scanf("%s%s",ch2,ch1);//两个栈合并
if(ch2[0]=='A')
{
root1=merge(root1,root2);
root2=0;
}else{
root2=merge(root2,root1);
root1=0;
}
}
}
}
}
return 0;
}