为了卡空间，在NOI2019弹跳这题中使用 set 作为树套树的内层。其中有一段实现是对于该节点下所有符合要求的 set 中元素取出并删除。

至于“符合要求”指：set 的元素为 pair<int,int>，要求 first 在区间 $[lh,rh]$ 中。

第一种实现是每次找到一个符合要求的，并删除。实测速度极慢。提交记录。这部分具体实现：

void Query(int u,int l,int r,int lw,int rw,int lh,int rh,int x){
	if(lw<=l&&rw>=r){
		set<pair<int,int> >::iterator it=
			lower_bound(TR(u).begin(),TR(u).end(),make_pair(lh,0));
		while(it!=TR(u).end()&&it->first<=rh)
			(d[it->second]<=x?void():pq.push(make_pair(d[it->second]=x,it->second))),
				TR(u).erase(it),
				it=lower_bound(TR(u).begin(),TR(u).end(),make_pair(lh,0));
		return;
	}
	int mid=(l+r)>>1;
	if(lw<=mid)
		Query(LS(u),l,mid,lw,rw,lh,rh,x);
	if(rw>mid)
		Query(RS(u),mid+1,r,lw,rw,lh,rh,x);
}

第二种实现是从第一个符合的开始往后遍历整个合法的区间，最后再删除一段区间。速度飞快。提交记录。具体实现如下：

void Query(int u,int l,int r,int lw,int rw,int lh,int rh,int x){
	if(lw<=l&&rw>=r){
		set<pair<int,int> >::iterator it=
			lower_bound(TR(u).begin(),TR(u).end(),make_pair(lh,0)),itt=it;
		while(it!=TR(u).end()&&it->first<=rh)
			(d[it->second]<=x?void():pq.push(make_pair(d[it->second]=x,it->second))),++it;
		TR(u).erase(itt,it);
		return;
	}
	int mid=(l+r)>>1;
	if(lw<=mid)
		Query(LS(u),l,mid,lw,rw,lh,rh,x);
	if(rw>mid)
		Query(RS(u),mid+1,r,lw,rw,lh,rh,x);
}

问了大佬说 set::iterator 的 ++ 复杂度也是 $O(logn)$ 级别的。那为什么会有这么大的速度差距呢？是因为常数小很多，还是因为 ++ 的复杂度为 $O(1)$，还是因为这样求一段区间时有势能之类的能均摊复杂度到 $O(1)$ 啊？