每日一题-CF1996G Penacony

异常明显的思路，考场上却不会，连确定一条边不选都没想到

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
int t,n,m,res;
pii a[200005];
struct tree{
	int mn,s,lz;
}tr[800005];
void push_up(int rt){
	tr[rt].s=0;
	tr[rt].mn=min(tr[ls].mn,tr[rs].mn);
	if(tr[rt].mn==tr[ls].mn)tr[rt].s+=tr[ls].s;
	if(tr[rt].mn==tr[rs].mn)tr[rt].s+=tr[rs].s;
}
void build(int rt,int l,int r){
	tr[rt].lz=0;
	if(l==r){
		tr[rt]=tree{0,1,0};
		return ;
	}
	build(ls,l,mid);build(rs,mid+1,r);
	push_up(rt);
}
void push_down(int rt){
	tr[ls].mn+=tr[rt].lz;
	tr[ls].lz+=tr[rt].lz;
	tr[rs].mn+=tr[rt].lz;
	tr[rs].lz+=tr[rt].lz;
	tr[rt].lz=0; 
}
void update(int rt,int l,int r,int ql,int qr,int k){
//	if(rt==1)printf("%d %d %d\n",ql,qr,k);
	if(ql<=l && qr>=r){
		tr[rt].mn+=k;
		tr[rt].lz+=k;
		return ;
	}else if(ql>r || qr<l)return ;
	push_down(rt);
	update(ls,l,mid,ql,qr,k);
	update(rs,mid+1,r,ql,qr,k);
	push_up(rt);
}
int query(){
	return n-tr[1].s;
}
struct node{
	int x,id;
}b[400005];
bool cmp(node x,node y){
	return x.x<y.x;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)scanf("%d%d",&a[i].fi,&a[i].se),b[i]=node{a[i].fi,i},b[i+m]=node{a[i].se,-i};
		build(1,1,n);
		for(int i=1;i<=m;i++){
			if(a[i].fi>=2)update(1,1,n,a[i].fi,a[i].se-1,1);
			else update(1,1,n,a[i].se,n,1);
		}
		sort(b+1,b+1+m+m,cmp);
		int la=0;
		res=query();
		while(b[la+1].x==1 && la+1<=m+m)la++;
		for(int i=2;i<=n;i++){
			while(b[la+1].x==i && la+1<=m+m){
				la++;
				if(b[la].id>0){
					int id=b[la].id;
					update(1,1,n,1,a[id].fi-1,1);
					update(1,1,n,a[id].fi,a[id].se-1,-1);
					update(1,1,n,a[id].se,n,1);
				}else{
					int id=-b[la].id;
					update(1,1,n,1,a[id].fi-1,-1);
					update(1,1,n,a[id].fi,a[id].se-1,1);
					update(1,1,n,a[id].se,n,-1);
				}
			}
//			if(i==3)printf("%d!!!!!!!!\n",query());
			res=min(res,query());
		}
		printf("%d\n",res);
	}
	return 0;
}