关于 P4093 的 BIT 套 map 写法

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-(x))

constexpr int N=1e5+9;
int n,m,ans;
struct node{
	int x,y_1,y_2;
}a[N];
map<int,int> tr[N];

void insert(int x,int y,int k){
	for(;x<N;x+=lowbit(x)){
		auto it=tr[x].upper_bound(y);
		if(it!=tr[x].begin()&&prev(it)->second>=k) continue;
		while(it!=tr[x].end()&&it->second<=k) it=tr[x].erase(it);
		tr[x][y]=k;
	}
}

int range_max(int x,int y){
	int res=0;
	for(;x;x-=lowbit(x)){
		auto it=tr[x].upper_bound(y);
		if(it==tr[x].begin()) continue;
		res=max(res,prev(it)->second);
	}
	return res;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].y_1=a[i].y_2=a[i].x;
	}
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		a[x].y_1=min(a[x].y_1,y);
		a[x].y_2=max(a[x].y_2,y);
	}
	for(int i=1;i<=n;i++){
		int res=range_max(a[i].y_1,a[i].x)+1;
		ans=max(ans,res);
		insert(a[i].x,a[i].y_2,res);
	}
	cout<<ans;
	return 0;
}