题目传送门：https://arc076.contest.atcoder.jp/tasks/arc076_d
题目大意：
有(m)把椅子，在数轴的(1sim m)坐标上，现在有(n)个人，他们想坐的椅子坐标需要满足(X_iin (-infty,l_i]igcup[r_i,infty))，你可以把任意多的椅子放在任意坐标（可为实数）处，问最少放多少把椅子可以让所有人都坐下？（陈独秀请你坐下）
首先这题要用到霍尔定理（Hall定理），我们令二分图两边的点集为(X)和(Y)，(omega(X))表示(Y)共有多少个点可以通过边集(E)和(X)相连，根据Hall定理有(forall X'subset X,|X'|leqslant|omega(X')|)
这题我们假定添加(t)个座位后，所有人都能坐下，那么就有(X'subset X,|X'|leqslant|omega(X')+t|Rightarrow|X'|-|omega(X')|leqslant t)，那么(t)的最小值为(max{|X'|-|omega(X')|})。但是直接遍历子集复杂度太高，我们可以转而遍历((L,R))的区间，若固定(L)，只需要求(max{|X'|+R})，我们可以用线段树完成这个操作，对于每个(L)，处理每个(R_i)，让([L,R_i])内全部+1，为了选择最大的(|X'|+R)，可以把所有节点初始化为(R)，然后直接线段树就好了
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=2e5;
vector<int>vec[N+10];
struct S1{
#define ls (p<<1)
#define rs (p<<1|1)
int tree[(N<<2)+10],Lazy[(N<<2)+10];
void Add_cnt(int p,int v){
tree[p]+=v;
Lazy[p]+=v;
}
void pushdown(int p){
if (!Lazy[p]) return;
Add_cnt(ls,Lazy[p]);
Add_cnt(rs,Lazy[p]);
Lazy[p]=0;
}
void build(int p,int l,int r){
if (l==r){
tree[p]=l;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
tree[p]=max(tree[ls],tree[rs]);
}
void Modify(int p,int l,int r,int x,int y){
if (x<=l&&r<=y){
Add_cnt(p,1);
return;
}
pushdown(p);
int mid=(l+r)>>1;
if (x<=mid) Modify(ls,l,mid,x,y);
if (y>mid) Modify(rs,mid+1,r,x,y);
tree[p]=max(tree[ls],tree[rs]);
}
int Query(int p,int l,int r,int x,int y){
if (x<=l&&r<=y) return tree[p];
pushdown(p);
int mid=(l+r)>>1,res=-inf;
if (x<=mid) res=max(res,Query(ls,l,mid,x,y));
if (y>mid) res=max(res,Query(rs,mid+1,r,x,y));
return res;
}
#undef ls
#undef rs
}ST;//Segment Tree
int main(){
int n=read(),m=read(),Ans=max(0,n-m);
for (int i=1;i<=n;i++){
int l=read(),r=read();
vec[l].push_back(r);
}
ST.build(1,0,m+1);
for (int i=0;i<=m;i++){
for (vector<int>::iterator it=vec[i].begin();it!=vec[i].end();it++) ST.Modify(1,0,m+1,i,*it);
Ans=max(Ans,ST.Query(1,0,m+1,i+1,m+1)-m-i-1);
}
printf("%d
",Ans);
return 0;
}