题意
模拟栈操作。有三种操作push,pop,peak分别代表从栈顶压入元素，删除栈顶元素，查询栈顶元素。但是，每个操作会给出一个时间戳，要求操作必须要按照时间戳来进行。但是对于每个peak必须马上给出查询结果。其中n<=50000,xi,ti<=1e9
分析
讲真，这种题必须结合样例才能明白让干嘛。如果暴力的话，对于每个peak的时间复杂度都是O(n)。所以我们想到了线段树。
1.因为t的值很大，所以我们要首先将t离散化（我因为离散化写丑了一开始还T了好几发）
2.将每个push的t和x对应的记录下来
3.对于每个操作push，我们在t的位置插入1，对于每个pop操作，我们在t的位置插入-1。对于每个peak操作，我们找到t左边的第一个t1，符合sum(t1 to t)>0,这时候和t1对应的x值就是答案。
思路是很好想的，然后就是操作3该怎么通过线段树来维护？
我们通过线段树来维护一个区间和，和一个最大后缀和，然后对于没个peak查询，所有从1到t的线段树的结点，从右往左找，如果加上当前结点的最大后缀和大于0的话，这个答案就一定在这个节点内，否则加上这个结点的区间和继续往左找。这里可以结合代码进行理解。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map> using namespace std;
const int maxn=+;
struct Ope{
string name;
int t,a;
}ope[maxn];
int n,kase;
int V[maxn],M[maxn];
int sumv[*maxn],max_suff[*maxn];
int v,x;
void maintain(int o){
sumv[o]=sumv[*o]+sumv[*o+];
max_suff[o]=max(max_suff[*o+],sumv[*o+]+max_suff[*o]);
}
void update(int o,int L,int R){
if(L==R){
sumv[o]+=x;
max_suff[o]+=x;
return ;
}
int M=L+(R-L)/;
if(v<=M)update(*o,L,M);
if(v>M)update(*o+,M+,R);
maintain(o);
return;
}
int tot,ans;
int ql,qr;
void solve(int o,int L,int R){
if(L==R){
ans=L;
return;
}
int M=L+(R-L)/;
if(tot+max_suff[*o+]>)
return solve(*o+,M+,R);
tot+=sumv[*o+];
return solve(*o,L,M);
}
void query(int o,int L,int R){
if(ans!=-)
return;
if(ql<=L&&qr>=R){
if(tot+max_suff[o]>){
solve(o,L,R);
}
else tot+=sumv[o];
return;
}
int M=L+(R-L)/;
if(M<qr)
query(*o+,M+,R);
if(M>=ql)
query(*o,L,M);
return;
}
int main(){
kase=;
while(scanf("%d",&n)!=EOF&&n){
printf("Case #%d:\n",++kase);
for(int i=;i<=n;i++){
cin>>ope[i].name;
if(ope[i].name=="push"){
scanf("%d%d",&ope[i].a,&ope[i].t);
}
if(ope[i].name=="pop"||ope[i].name=="peak"){
scanf("%d",&ope[i].t);
}
V[i]=ope[i].t;
}
sort(V+,V++n);
for(int i=;i<=n;i++){
if(ope[i].name=="push"){
int tt=lower_bound(V+,V++n,ope[i].t)-V;
M[tt]=ope[i].a;
}
}
/* for(int i=1;i<=n;i++){
int tt=lower_bound(V+1,V+1+n,ope[i].t)-V;
cout<<tt<<endl;
}*/ memset(sumv,,sizeof(sumv));
memset(max_suff,,sizeof(max_suff)); for(int i=;i<=n;i++){
if(ope[i].name=="push"){
v=lower_bound(V+,V++n,ope[i].t)-V;
x=;
update(,,n);
}
else if(ope[i].name=="pop"){
v=lower_bound(V+,V++n,ope[i].t)-V;
x=-;
update(,,n);
}
else{
ql=,qr=lower_bound(V+,V++n,ope[i].t)-V;
tot=,ans=-;
query(,,n);
printf("%d\n",ans==-?-:M[ans]);
}
}
}
return ;
}