题意：
给你两个栈，多了个合并操作，然后让你模拟
题解：
很容易想到O(1)的单个栈操作，O(n)的合并操作，这样肯定超时，所以我们要将时间复杂度均摊一下，让每个操作都是logn的，于是用上了线段树模拟。
线段树考虑染色，线段树的区间代表的是操作编号，0代表为A栈，1代表为B栈，每次merge 就把1到i这个区间染成指定颜色，然后pop就在线段树中找最右边的对应颜色的点。这样每次操作都是logn
不过官方题解给的是O(n)的解法，反正我是没想到的，感觉智商被压制。
第一份代码是线段树O(nlogn)，第二份代码是数组模拟O(n)。也就只能快400ms
Joint Stacks
比较简单巧妙的一个做法是引入一个新的栈C，每次合并的时候就把A和B合并到C上，然后把A和B都清空. push还是按正常做，pop注意当遇到要pop的栈为空时，因为题目保证不会对空栈进行pop操作，所以这时应直接改为对C栈进行pop操作. 这样做因为保证每个元素最多只在一次合并中被处理到，pop和push操作当然也是每个元素只做一次，所以总复杂度是O(N)的. 另一种做法是用链表来直接模拟，复杂度也是O(N)，但代码量稍大一些.
#include<bits/stdc++.h>
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std; const int N=1e5+;
int n,tr[N<<],lazy[N<<],dt[N],now,ic=;
char op[],x[],y[]; inline void pd(int rt)
{
if(lazy[rt])
{
if(tr[rt<<])tr[rt<<]=lazy[rt],lazy[rt<<]=lazy[rt];
if(tr[rt<<|])tr[rt<<|]=lazy[rt],lazy[rt<<|]=lazy[rt];
lazy[rt]=;
}
} void update(int L,int R,int c,int l=,int r=n,int rt=)
{
if(l==r&&L==R){tr[rt]=c;return;}
if(L<=l&&r<=R)
{
if(tr[rt])tr[rt]=c,lazy[rt]=c;
return;
}
pd(rt);
int m=(l+r)>>;
if(L<=m)update(L,R,c,ls);
if(R>m)update(L,R,c,rs);
tr[rt]=tr[rt<<]|tr[rt<<|];
} int pop(int x,int l=,int r=n,int rt=)
{
if(l==r){tr[rt]=;return l;}
pd(rt);
int ans,m=(l+r)>>;
if(tr[rt<<|]&x)ans=pop(x,rs);
else ans=pop(x,ls);
tr[rt]=tr[rt<<]|tr[rt<<|];
return ans;
}
int main(){
while(scanf("%d",&n),n)
{
printf("Case #%d:\n",ic++);
mst(tr,),mst(lazy,);
F(i,,n)
{
scanf("%s",op);
if(op[]=='p'&&op[]=='u')
{
scanf("%s%d",x,dt+i);
if(x[]=='A')update(i,i,);else update(i,i,);
}else if(op[]=='p')
{
scanf("%s",x);
if(x[]=='A')now=pop();else now=pop();
printf("%d\n",dt[now]);
}else
{
scanf("%s%s",x,y);
if(x[]=='A')update(,i,);else update(,i,);
}
}
}
return ;
}
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef pair<int,int>P; const int N=5e4+;
int eda,edb,edc,n,tp,ic=,c[N];
char op[],x[],y[];
P a[N],b[N]; int main()
{
while(scanf("%d",&n),n)
{
printf("Case #%d:\n",ic++);
eda=edb=edc=;
F(i,,n)
{
scanf("%s",op);
if(op[]=='p'&&op[]=='u')
{
scanf("%s%d",x,&tp);
if(x[]=='A')a[++eda].first=tp,a[eda].second=i;
else b[++edb].first=tp,b[edb].second=i;
}else if(op[]=='p')
{
scanf("%s",x);
if(x[]=='A')
{
if(eda)printf("%d\n",a[eda--].first);
else printf("%d\n",c[edc--]);
}else
{
if(edb)printf("%d\n",b[edb--].first);
else printf("%d\n",c[edc--]);
}
}else
{
scanf("%s%s",x,y);
for(int ii=,jj=;ii<=eda||jj<=edb;)
{
if(ii<=eda&&jj<=edb)
{
if(a[ii].second<b[jj].second)c[++edc]=a[ii].first,ii++;
else c[++edc]=b[jj].first,jj++;
}else if(ii<=eda)c[++edc]=a[ii].first,ii++;
else if(jj<=edb)c[++edc]=b[jj].first,jj++;
}
eda=,edb=;
}
} }
return ;
}