Description
在如今的网络中，TCP是一种被广泛使用的网络协议，它在传输层提供了可靠的通信服务。众所周知，网络是存在
时延的，例如用户先后向服务器发送了两个指令op1和op2，并且希望服务器先处理指令op1，再处理指令op2；但由
于网络时延，这两个指令可能会失序到达，而导致服务器先执行了指令op2，这是我们不希望看到的。TCP协议拥有
将失序到达的报文按顺序重组的功能，一种方法是给每一个报文打上一个时间戳。而你今天要实现的功能比这个要
简单很多。我们需要你维护一个服务器，这个服务器的功能是一个简单的栈，你会接收三种用户的指令：
push x t --- 表示将x元素入栈，这条指令的时间戳为t
pop t --- 表示将栈顶元素弹出，这条指令的时间戳为t
peak t --- 用户询问现在栈顶元素的值，这条指令的时间戳为t
当一条时间戳为t的指令到达时，你需要进行如下处理：
1.将所有之前执行的时间戳大于t的push和pop指令全部撤销
2.执行当前这条指令
3.按时间戳顺序重新执行在第1步被撤销的指令
注意你不需要撤销以及重新执行之前已经执行过的peak指令
也就是说每一条peak指令只有在它到达的时候会被执行一次。
我们保证每一条指令的时间戳都是唯一的；
若你在需要执行一条pop指令时发现当前栈为空，则当前你可以忽略这条指令。
Input
第一行包含一个整数n，表示指令总数。
接下来n行按指令到达服务器的顺序给出每一条指令，有三种类型
push x t
pop t
peak t
1 <= n <= 300000，0 <= x，t <= 1000000000
Output
对于每一条peak指令，输出对应的答案占一行；若栈为空，输出-1。
用线段树维护操作对应的括号序列的前缀和（push=1,pop=-1,peak=0,未执行=0），查询相当于查询一个位置向左第一个小于指定值的位置。
#include<bits/stdc++.h>
const int N=;
char buf[N*],*ptr=buf;
int _(){
int x=;
while(*ptr<)++ptr;
while(*ptr>)x=x*+*ptr++-;
return x;
}
int n,ts[N],qs[N][],tp=,vs[N];
int _x,_a,_p;
int min(int a,int b){return a<b?a:b;}
struct node{
node*lc,*rc;
int L,R,M;
int mn,a;
void add(int x){
mn+=x,a+=x;
}
void dn(){
if(a){
lc->add(a);
rc->add(a);
a=;
}
}
void up(){
mn=min(lc->mn,rc->mn);
}
void add(){
if(_x<=L)return add(_a);
dn();
if(_x<=M)lc->add();
rc->add();
up();
}
int at(){
if(L==R)return mn;
dn();
return (_x<=M?lc:rc)->at();
}
bool find(){
if(mn>=_a)return ;
if(L==R)return _p=R+,;
dn();
if(_x>M&&rc->find())return ;
return lc->find();
}
}ns[N*],*np=ns,*rt;
node*build(int L,int R){
node*w=np++;
w->L=L,w->R=R;
if(L<R){
int M=w->M=L+R>>;
w->lc=build(L,M);
w->rc=build(M+,R);
}
return w;
}
int $(int x){
return std::lower_bound(ts,ts+tp,x)-ts;
}
int main(){
fread(buf,,sizeof(buf),stdin);
n=_();
ts[tp++]=-;
for(int i=;i<=n;++i){
qs[i][]=_();
qs[i][]=_();
if(qs[i][]==)ts[tp++]=qs[i][]=_();
else ts[tp++]=qs[i][];
}
std::sort(ts,ts+tp);
rt=build(,tp-);
vs[]=-;
for(int i=;i<=n;++i){
if(qs[i][]==){
_x=$(qs[i][]);
vs[_x]=qs[i][];
_a=,rt->add();
}else if(qs[i][]==){
_x=$(qs[i][]);
_a=-,rt->add();
}else{
_x=$(qs[i][]);
_a=rt->at();
_p=;
rt->find();
printf("%d\n",vs[_p]);
}
}
return ;
}