用两个栈模拟，并保存每个点的时间戳。每次合并的时候记录合并时的时间戳mcnt和此时的topa和topb记做ta、tb。

每次pop的时候，如果栈的top的时间戳大于mcnt，则普通地pop，否则就在两个栈ta和tb下面找时间戳最大且还没pop掉的。然后用bj[时间戳]来标记已经pop了。

#include 
     
      #include 
      
       #define N 100005using namespace std;struct node{    int id,v;}a[N],b[N];int bj[N],n,topa,topb,cnt,ele,ta,tb,mcnt,cas;char op[50],st;void popc(){    while(bj[a[ta].id])ta--;    while(bj[b[tb].id])tb--;    if(a[ta].id>b[tb].id){        printf("%d\n",a[ta].v);        bj[a[ta].id]=1;    }else {        printf("%d\n",b[tb].v);        bj[b[tb].id]=1;    }}int main() {    while(scanf("%d",&n),n){        printf("Case #%d:\n",++cas);        topa=topb=cnt=mcnt=0;        memset(bj,0,sizeof bj);        for(int i=1;i<=n;i++){            scanf("%s %c",op,&st);            if(op[1]=='u'){                 scanf("%d",&ele);                if(st=='A')                    a[++topa]=(node){++cnt,ele};                else                    b[++topb]=(node){++cnt,ele};            }else if(op[1]=='o'){                if(st=='A'){                    if(a[topa].id>mcnt){                        printf("%d\n",a[topa].v);                        bj[a[topa].id]=1;                        topa--;                    }                    else                        popc();                }else{                    if(b[topb].id>mcnt){                        printf("%d\n",b[topb].v);                        bj[b[topb].id]=1;                        topb--;                    }                    else                        popc();                    }            }else if(op[1]=='e'){                scanf(" %c",&st);                mcnt=cnt;                ta=topa;                tb=topb;            }        }    }    return 0;}
      
     

 

wa了好几发，结果原因是 “if(a[topa].id>mcnt)”写的是>=，为什么等于不可以呢，因为popc函数里没有top--，这样下一次top的值可能已经pop掉了。那如果在popc里面top--呢，也不行，因为pop栈a的ta时，可能在pop栈b，这样to pa--的话就错了。这题用优先队列也很方便。

　　

#include 
     
      #include 
      
       #define prq priority_queue#define pii pair
       
        #define mp(a,b) make_pair(a,b)#define cl(a) while(!a.empty())a.pop();using namespace std;prq
        
          a,b,c;int n,cas;void pop(prq
         
           &q){    if(!q.empty()){        printf("%d\n",q.top().second);        q.pop();    }else{        printf("%d\n",c.top().second);        c.pop();    }}void push(prq
          
            &q){ while(!q.empty()){ c.push(q.top()); q.pop(); }}int main() { while(scanf("%d",&n),n){ printf("Case #%d:\n",++cas); cl(a);cl(b);cl(c); int cnt=0; while(n--){ char op[10],st; scanf("%s %c",op,&st); if(op[1]=='u'){ int x; scanf("%d",&x); if(st=='A') a.push(mp(++cnt,x)); else b.push(mp(++cnt,x)); }else if(op[1]=='o'){ if(st=='A') pop(a); else pop(b); }else{ scanf(" %c",&st); push(a);push(b); } } }}