题意：
n个人抢m个凳子，第i个人做的位置必须小于li或大于ri，问最少几个人坐不上。
这是一个二分图最大匹配的问题，hall定理可以用来求二分图最大匹配。
关于hall定理及证明，栋爷博客里有：http://blog.csdn.net/werkeytom_ftd/article/details/65658944
可以推出答案为$max{|x|-Γ(X)}$，x为左侧点的一个子集，Γ(X)为这些点能到达的右侧点的集合。
证明:
因为二分图有完美匹配的充要条件是对于所有的x都有Γ(X)>=|x|,所以至少要再加$max{|x|-Γ(X)}$个点才能让这张图有完美匹配。
考虑向右侧新加$max{|x|-Γ(X)}$个点，与左侧所有点都有边，显然对于所有的x都有Γ(X)>=|x|，既这张图有完美匹配。
所以最少加$max{|x|-Γ(X)}$个点。
然后就可以枚举Γ(X)，用线段树维护|x|。
#include<bits/stdc++.h>
#define N 200005
#define pd push_back
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
using namespace std;
int n,m;
vector<int>s[N];
int t[N<<2],f[N<<2];
void build(int x,int l,int r)
{
if(l==r){t[x]=l;return ;}
int mid=(l+r)>>1;build(ls);build(rs);
t[x]=max(t[x<<1],t[x<<1|1]);
}
void add(int x,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)
{
t[x]++;f[x]++;return ;
}
int mid=(l+r)>>1;
if(ll<=mid)add(ls,ll,rr);
if(rr>mid)add(rs,ll,rr);
t[x]=f[x]+max(t[x<<1],t[x<<1|1]);
}
int qur(int x,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)return t[x];
int mid=(l+r)>>1;
if(ll>mid)return f[x]+qur(rs,ll,rr);
if(rr<=mid)return f[x]+qur(ls,ll,rr);
return f[x]+max(qur(ls,ll,rr),qur(rs,ll,rr));
}
int main()
{
scanf("%d%d",&n,&m);
int ans=0;
for(int i=1;i<=n;i++)
{
int t1,t2;scanf("%d%d",&t1,&t2);s[t1].pd(t2);
}
build(1,0,m+1);
for(int i=0;i<=m;i++)
{
for(auto j:s[i])add(1,0,m+1,0,j);
ans=max(ans,qur(1,0,m+1,i+1,m+1)-i-m-1);
}
printf("%d
",max(n-m,ans));
return 0;
}