很容易想到线段树，把插入看成1，弹出看成-1，做后缀和后用线段树维护 这题就是一个区间加减和区间最大值问题了 （区间最大值大于0表示栈顶在此）
#include<stdio.h> #include<algorithm> #define cint const int & #define M 131072 int n,aim,type,x[M]; bool flag; struct node{int tag,max;}t[M+5<<1]; inline void maintain(cint k) { t[k].max+=t[k].tag; if (k<M) { t[k<<1].tag+=t[k].tag; t[k<<1|1].tag+=t[k].tag; } t[k].tag=0; } void change(cint k,cint l,cint r) { if (r<=aim) { t[k].tag+=type; maintain(k); return; } if (t[k].tag) maintain(k); int mid=l+r>>1; if (mid<aim) change(k<<1|1,mid+1,r); change(k<<1,l,mid); maintain(k<<1|1); t[k].max=std::max(t[k<<1].max,t[k<<1|1].max); } void top(cint k) { if (t[k].tag) maintain(k); if (t[k].max<=0) return; if (M<=k) { printf("%d\n",x[k-M+1]); flag=1; return; } if (!flag) top(k<<1|1); if (!flag) top(k<<1); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&aim,&type); if (type==0) type=-1; else scanf("%d",x+aim); change(1,1,M); flag=0; top(1); if (!flag) puts("-1"); } }