Splay 暴力维护节点信息即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int delta,t1,t2,t3,k[1000005],ch[1000005][2],fa[1000005],a[1000005],t[1000005],n,ind,root,opera[1000005][2],seq[1000005],cnt=0;
void rotate(int p){
int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
ch[q][x]=ch[p][x^1]; fa[ch[q][x]]=q;
ch[p][x^1]=q; fa[q]=p; fa[p]=y;
if(y)if(ch[y][0]==q)ch[y][0]=p;
else if(ch[y][1]==q)ch[y][1]=p;}
void splay(int p){
int x=p,y;
for(;y=fa[x];rotate(x))if(fa[y])rotate((ch[fa[y]][0]==y)==(ch[y][0]==x)?y:x);
root=x;}
int prefix(int p){
if(p==0) return 0;
splay(p);
int x=ch[p][0];
while(x&&ch[x][1]) x=ch[x][1];
return x;}
int suffix(int p){
if(p==0) return 0;
splay(p);
int x=ch[p][1];
while(x&&ch[x][0]) x=ch[x][0];
return x;}
int minpt(){
int x=root;
while(x&&ch[x][0]) x=ch[x][0];
return x;}
int maxpt(){
int x=root;
while(x&&ch[x][1]) x=ch[x][1];
return x;}
void insert(int v){
if(root==0) root=++ind, k[ind]=v;
else{
int x=root,tx=root;
while(tx) x=tx, tx=ch[x][k[x]<v];
ch[x][k[x]<v]=++ind;
k[ind]=v; fa[ind]=x;
splay(ind);
}}
int search(int v){
int p=root;
while(k[p]-v&&ch[p][k[p]<v]) p=ch[p][k[p]<v];
return p;}
void remove(int p){
if(p==0)return;
splay(p);
int lr=ch[p][0],rr=ch[p][1];
if(lr==0) {root=rr, fa[rr]=0; return;}
int tm=lr;
root=lr;
while(tm&&ch[tm][1]) tm=ch[tm][1];
if(tm) splay(tm);
ch[root][1]=rr; fa[rr]=root;
}
void print(int p){
if(p==0) return;
print(ch[p][0]);
printf("%d ",k[p]);
print(ch[p][1]);}
void modify(int p,int l,int r,int ml,int mr,int k){
if(l>mr||r<ml) return;
if(l>=ml&&r<=mr){ t[p]+=k; a[p]+=k; return;}
t[p*2]+=t[p], t[p*2+1]+=t[p];
a[p*2]+=t[p], a[p*2+1]+=t[p]; t[p]=0;
modify(p*2,l,(l+r)/2,ml,mr,k);
modify(p*2+1,(l+r)/2+1,r,ml,mr,k);
a[p]=min(a[p*2],a[p*2+1]);}
int query(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0x7fffffff;
if(l>=ql&&r<=qr) return a[p];
t[p*2]+=t[p], t[p*2+1]+=t[p];
a[p*2]+=t[p], a[p*2+1]+=t[p]; t[p]=0;
return min(query(p*2,l,(l+r)/2,ql,qr),query(p*2+1,(l+r)/2+1,r,ql,qr));}
int getvalue(int pos){
int t=query(1,1,cnt,pos,pos);
if(t>=0x3f3f3f3) return 0;
else return t;}
void putvalue(int pos,int k){
int ori=query(1,1,cnt,pos,pos);
modify(1,1,cnt,pos,pos,-ori);
modify(1,1,cnt,pos,pos,k);}
int main(){
memset(a,0x3f,sizeof a);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&t1);
if(t1==1) scanf("%d",&t2);
opera[i][0]=t1, opera[i][1]=t2;
if(t1==1) seq[cnt++]=t2;
}
sort(seq,seq+cnt);
for(int i=1;i<=n;i++)
opera[i][1]=upper_bound(seq,seq+cnt,opera[i][1])-seq;
for(int i=1;i<=n;i++){
t1=opera[i][0], t2=opera[i][1];
if(t1==1){
insert(t2);
putvalue(t2,(t3=max(getvalue(k[prefix(search(t2))]),getvalue(k[suffix(search(t2))]))+1));
printf("%d
",t3);
}
if(t1==2){
int p=k[minpt()];
int lb=p,rb=p,sd=getvalue(p);
for(int i=17;i>=0;i--) if(rb+(1<<i)<=cnt&&query(1,1,cnt,rb+1,rb+(1<<i))>sd) rb=rb+(1<<i);
for(int i=17;i>=0;i--) if(lb-(1<<i)>0&&query(1,1,cnt,lb-(1<<i),lb-1)>sd) lb=lb-(1<<i);
modify(1,1,cnt,1,cnt,+1);
modify(1,1,cnt,lb,rb,-1);
putvalue(p,1);
printf("%d
",sd);
}
if(t1==3){
int p=k[maxpt()];
int lb=p,rb=p,sd=getvalue(p);
for(int i=17;i>=0;i--) if(rb+(1<<i)<=cnt&&query(1,1,cnt,rb+1,rb+(1<<i))>sd) rb=rb+(1<<i);
for(int i=17;i>=0;i--) if(lb-(1<<i)>0&&query(1,1,cnt,lb-(1<<i),lb-1)>sd) lb=lb-(1<<i);
modify(1,1,cnt,1,cnt,+1);
modify(1,1,cnt,lb,rb,-1);
putvalue(p,1);
printf("%d
",sd);
}
if(t1==4){
int p=k[minpt()];
int lb=p,rb=p,sd=getvalue(p);
for(int i=17;i>=0;i--) if(rb+(1<<i)<=cnt&&query(1,1,cnt,rb+1,rb+(1<<i))>sd) rb=rb+(1<<i);
for(int i=17;i>=0;i--) if(lb-(1<<i)>0&&query(1,1,cnt,lb-(1<<i),lb-1)>sd) lb=lb-(1<<i);
modify(1,1,cnt,lb,rb,-1);
putvalue(p,0x3f3f3f3f);
remove(minpt());
printf("%d
",sd);
}
if(t1==5){
int p=k[maxpt()];
int lb=p,rb=p,sd=getvalue(p);
for(int i=17;i>=0;i--) if(rb+(1<<i)<=cnt&&query(1,1,cnt,rb+1,rb+(1<<i))>sd) rb=rb+(1<<i);
for(int i=17;i>=0;i--) if(lb-(1<<i)>0&&query(1,1,cnt,lb-(1<<i),lb-1)>sd) lb=lb-(1<<i);
modify(1,1,cnt,lb,rb,-1);
putvalue(p,0x3f3f3f3f);
remove(maxpt());
printf("%d
",sd);
}
}
}