题目大意
分析
倒着跑LIS表示以i为开头的LIS，于是对于删除可以暴力重算前10棵树。而对于种树，因为高度不超过10且高度两两不同，所以暴力重算比它矮的10棵树即可。对于需要重算的点，将其从线段树中删掉然后重算即可。我们要维护一个关于x轴的线段树和一个关于y轴的线段树，重算下边的点需要使用关于x轴的线段树，而重算左边的点需要另一个线段树，注意在修改一个点的时候应该将它在两课线段树中的信息同时修改
我们可以x轴y轴各开一个堆，这样就可以每次取出最小的几个进行操作了
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int n,m,dx[4001000],dy[4001000],pl[200100],h[200100],Ans,N;
bool is[200100];
priority_queue<pair<int,int> >x,y;
stack<pair<int,int> >xa,ya;
inline void upx(int le,int ri,int wh,int pl,int k){
if(le==ri){dx[wh]=k;return;}
int mid=(le+ri)>>1;
if(mid>=pl)upx(le,mid,wh<<1,pl,k);
else upx(mid+1,ri,wh<<1|1,pl,k);
dx[wh]=max(dx[wh<<1],dx[wh<<1|1]);
}
inline void upy(int le,int ri,int wh,int pl,int k){
if(le==ri){dy[wh]=k;return;}
int mid=(le+ri)>>1;
if(mid>=pl)upy(le,mid,wh<<1,pl,k);
else upy(mid+1,ri,wh<<1|1,pl,k);
dy[wh]=max(dy[wh<<1],dy[wh<<1|1]);
}
inline int qx(int le,int ri,int wh,int xx,int yy){
if(le>=xx&&ri<=yy)return dx[wh];
int mid=(le+ri)>>1,res=0;
if(mid>=xx)res=max(res,qx(le,mid,wh<<1,xx,yy));
if(mid<yy)res=max(res,qx(mid+1,ri,wh<<1|1,xx,yy));
return res;
}
inline int qy(int le,int ri,int wh,int xx,int yy){
if(le>=xx&&ri<=yy)return dy[wh];
int mid=(le+ri)>>1,res=0;
if(mid>=xx)res=max(res,qy(le,mid,wh<<1,xx,yy));
if(mid<yy)res=max(res,qy(mid+1,ri,wh<<1|1,xx,yy));
return res;
}
int main(){
int i,j,k,X,Y;
scanf("%d%d",&n,&m);
N=m+20;
for(i=1;i<=m;i++){
scanf("%d",&k);
if(k==1){
//h小,维护高度,Y
scanf("%d%d",&pl[i],&h[i]);
x.push(make_pair(-pl[i],i));
h[i]+=m-i;
while(!y.empty()){
if(-y.top().first<=h[i]){
if(!is[pl[y.top().second]])ya.push(y.top());
upy(1,n,1,pl[y.top().second],0);
y.pop();
}else break;
}
ya.push(make_pair(-h[i],i));
while(!ya.empty()){
y.push(ya.top()),ya.pop();
Y=qy(1,n,1,pl[y.top().second]+1,n)+1;
upx(1,N,1,-y.top().first,Y);
upy(1,n,1,pl[y.top().second],Y);
}
Ans=dy[1];
}else {
scanf("%d",&X);
while(X){
X--;
if(X){
xa.push(x.top());
x.pop();
upx(1,N,1,h[xa.top().second],0);
}else break;
}
upy(1,n,1,-x.top().first,0);
upx(1,N,1,h[x.top().second],0);
is[-x.top().first]=1;
x.pop();
while(!xa.empty()){
x.push(xa.top()),xa.pop();
int Y=qx(1,N,1,h[x.top().second]+1,N)+1;
upy(1,n,1,-x.top().first,Y);
upx(1,N,1,h[x.top().second],Y);
}
Ans=dx[1];
}
printf("%d
",Ans);
}
return 0;
}