线段树 100pts hack没过，玄关求条

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m,tot,cnt,a[1005],b[1005],num[10005],tag[N>>2],segtr[N>>2];
void build(int rt,int l,int r){
	if(l==r){
		segtr[rt]=0;
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	segtr[rt]=segtr[rt<<1]&segtr[rt<<1|1];
}
void push_down(int rt){
	if(tag[rt])segtr[rt<<1]=segtr[rt<<1|1]=tag[rt<<1]=tag[rt<<1|1]=1,tag[rt]=0;
}
void update(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		segtr[rt]=tag[rt]=1;
		return;
	}
	push_down(rt);
	int mid=l+r>>1;
	if(ql<=mid)update(rt<<1,l,mid,ql,qr);
	if(qr>mid)update(rt<<1|1,mid+1,r,ql,qr);
	segtr[rt]=segtr[rt<<1]&segtr[rt<<1|1];
}
int search(int x){
	return lower_bound(num+1,num+tot+1,x)-num;
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return segtr[rt];
	push_down(rt);
	int mid=l+r>>1;
	bool ans=1;
	if(ql<=mid)ans&=query(rt<<1,l,mid,ql,qr);
	if(qr>mid)ans&=query(rt<<1|1,mid+1,r,ql,qr);
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>a[i]>>b[i];
		num[++cnt]=a[i],num[++cnt]=b[i],num[++cnt]=b[i]+1;
	}
	sort(num+1,num+cnt+1);
	tot=unique(num+1,num+cnt+1)-num-1;
	build(1,1,tot);
	int ans=0;
	for(int i=m;i>=1;--i){
		int l=search(a[i]),r=search(b[i]);
		if(!query(1,1,tot,l,r)){
			ans++;
			update(1,1,tot,l,r);
		}
	}
	cout<<ans<<endl;
	return 0;
}