本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 11:46:29

Link

之前写的题解

发现每次删除或加入影响的点数量很少，考虑暴力将这些点拆出来再依次加入。

那么分为下标和高度两维考虑，分别开一个线段树，这样才能够让每次删除与插入达到 $\mathrm{O(\log n)}$ 的级别。

我用两个堆来存两维最小的 $10$ 棵树的信息。需要时刻注意这两个堆之间的联动关系，如删除的时候要注意另一个堆中的元素要删除（我用了一个标记数组），插入的时候要同时插入另一个堆。

答案又另开了一个可删堆来存，非常唐。

实际上答案直接从这两棵线段树中任一棵查一个全局最大值即可。

代码写得比之前要好读一些。

code

const int N=2e5+50;

struct Seg_Tree{
	int t[N<<2];
	void pushup(int x){t[x]=max(t[ls],t[rs]);}
	void update(int x,int l,int r,int c,int a){
		if(l==r){
			t[x]=a;
			return;
		}
		if(c<=mid)
			update(ls,l,mid,c,a);
		else
			update(rs,mid+1,r,c,a);
		pushup(x);
	}
	int query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R)
			return t[x];
		int mx=0;
		if(L<=mid)
			mx=max(mx,query(ls,l,mid,L,R));
		if(R>mid)
			mx=max(mx,query(rs,mid+1,r,L,R));
		return mx;
	}
}T1,T2;
bool tag[N];
priority_queue<pir>he,at;\/\/高度和下标的堆，插入和删除时要从这两个堆中找会影响到的数

pir tmp[15];int tot;

int f[N];
priority_queue<int>ans,del;

int lim;

void calc1(pir x){\/\/插入高度最小的
	int i=x.fi,h=x.se;
	f[i]=T1.query(1,1,lim,i+1,lim)+1;
	T1.update(1,1,lim,i,f[i]);
	T2.update(1,1,lim,h,f[i]);
	ans.push(f[i]);
	he.push({-h,i});
	
}

void calc2(pir x){\/\/插入下标最小的
	int i=x.fi,h=x.se;
	f[i]=T2.query(1,1,lim,h+1,lim)+1;
	T1.update(1,1,lim,i,f[i]);
	T2.update(1,1,lim,h,f[i]);
	ans.push(f[i]);
	at.push({-i,h});
}

int get_ans(){\/\/获取答案，这里的答案用了一个堆，这个堆需要支持删除元素，所以又开了个del
	while(!del.empty()&&ans.top()==del.top())
		ans.pop(),del.pop();
	if(ans.empty())\/\/WA on 2
		return 0;
	return ans.top();
}

signed main(){
	int n=read(),m=read();
	lim=m+10;
	for(int i=m;i>=1;i--){
		if(read()==1){
			int x=read(),height=read()+i;\/\/偏移
			tot=0;
			while(!he.empty()&&-he.top().fi<height){\/\/比自己矮的树
				if(!tag[he.top().se]){\/\/没被删过
					tmp[++tot].fi=he.top().se,tmp[tot].se=-he.top().fi;
					del.push(f[tmp[tot].fi]);
					T1.update(1,1,lim,tmp[tot].fi,0);
					T2.update(1,1,lim,tmp[tot].se,0);\/\/删除
				}
				he.pop();
			}
			tmp[++tot]={x,height};\/\/插入
			at.push({-x,height});\/\/另一个堆也要记得插入
			while(tot)\/\/剩下的插回树上
				calc1(tmp[tot--]);
		}else{
			int x=read();
			tot=0;
			while(!at.empty()&&tot<x){
				tmp[++tot].fi=-at.top().fi,tmp[tot].se=at.top().se;\/\/必定没被删除过
				del.push(f[tmp[tot].fi]);
				T1.update(1,1,lim,tmp[tot].fi,0);
				T2.update(1,1,lim,tmp[tot].se,0);\/\/删除
				at.pop();
			}
			tag[tmp[tot].fi]=1;\/\/删除标记
			f[tmp[tot].fi]=0;\/\/清空
			tot--;\/\/删掉这个元素
			while(tot)\/\/插回来
				calc2(tmp[tot--]);
		}
		print(get_ans()),pc('\n');
	}
	return 0;
}