请注意，这是正解

考虑设 $f_i$ 表示在第 $i$ 个人是女生时，在 $[1,i]$ 当中最多有多少个人是女生。特别的，如果 $f_i=0$ 则表示该位置不能是女生。

那么我们考虑进行 dp，很显然 dp 式子大概是：

我们来考虑 $k$ 应该满足哪些条件。

1. 不应存在一条限制覆盖区间 $[k,i]$。
2. 不应存在一条限制被区间 $(k,i)$ 包含。

对于第一个条件，显然能够算出距离你最近的满足条件的 $k$ 是多少；对于第二个条件，显然能够算出距离你最远的满足条件的 $k$ 是多少。

所以满足条件的 $k$ 一定是一个区间，随便用什么东西维护一下 $f$ 的 RMQ 即可，我采用的是线段树，$O(n\log n)$ 解决战斗。

注意到，满足条件的 $k$ 的区间在 $i$ 不断变大时，左端点单调不降，右端点单调不降，所以用单调队列维护那个最小值即可 $O(n)$ 解决战斗。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll N=2e5+10;
const ll M=1e5+10;
struct node{ll L,R;}dat[M];
bool cmp1(node x,node y){return x.L<y.L;} 
bool cmp2(node x,node y){return x.R>y.R;}
bool cmp3(node x,node y){return x.R<y.R;}
bool cmp4(node x,node y){return x.L>y.L;}
ll n,m,lft[N],rgt[N],top,f[N],maxx[N<<2];
inline void push_up(ll x){maxx[x]=max(maxx[lc],maxx[rc]);}
void chg(ll x,ll l,ll r,ll p,ll v){
	if(l==r){maxx[x]=v;return;}
	if(p<=mid) chg(lc,l,mid,p,v);
	else chg(rc,mid+1,r,p,v);
	push_up(x);
}
ll query(ll x,ll l,ll r,ll L,ll R){
	if(L<=l&&r<=R) return maxx[x];
	ll ret=-1;
	if(L<=mid) ret=max(ret,query(lc,l,mid,L,R));
	if(R>mid) ret=max(ret,query(rc,mid+1,r,L,R));
	return ret; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	if(m==0){cout<<n;return 0;}
	for(ll i=1;i<=m;i++) cin>>dat[i].L>>dat[i].R;
	for(ll i=1;i<=n;i++) lft[i]=rgt[i]=i;
	sort(dat+1,dat+1+m,cmp1);top=1;
	ll minn=-1;
	for(ll i=1;i<=n;i++){
		while(top<=m&&dat[top].L<=i){minn=max(minn,dat[top].R);top++;}
		rgt[i]=max(rgt[i],minn);
	}
	minn=n;
	sort(dat+1,dat+1+m,cmp2);top=1;
	for(ll i=n;i>=1;i--){
		while(top<=m&&dat[top].R>=i){minn=min(minn,dat[top].L);top++;}
		lft[i]=min(lft[i],minn);
	}
	sort(dat+1,dat+1+m,cmp3);top=1;
	ll now=0;minn=1;
	for(ll i=1;i<=n;i++){
		while(now<n&&rgt[now+1]<i) now++;
		if(i==1) f[i]=1;
		else{
			if(minn>min(lft[i]-1,now)) f[i]=0;
			else{
				f[i]=query(1,1,n,minn,min(lft[i]-1,now));
				if(f[i]) f[i]++;
			}
		}
		if(top==1) f[i]=max(f[i],1);
		chg(1,1,n,i,f[i]);
		while(top<=m&&dat[top].R<=i){minn=max(minn,dat[top].L);top++;}
	}
	sort(dat+1,dat+1+m,cmp4);
	ll ans=0;
	for(ll i=n;i>=1;i--){
		ans=max(ans,f[i]);
		if(dat[1].L>=i) break;
	}
	if(ans==0) cout<<"-1";
	else cout<<ans; 
	return 0;
}

膜爆了。㔻。

设 $dp_i$ 表示在第 $i$ 个人是母的的情况下，前 $i$ 个人有多少个人是母的，注意这里设的是位置而不是区间。

那么显然存在一个位置 $j$ 使得 $i$ 可以从 $j$ 转移过来。

考虑 $j$ 的合法性。

首先题目中说了对于任意一个区间要保证都仅仅存在一个母的，这可以转化为：任意一个区间都最多包含一个母的，最少包含一个母的。

我们对于任意一个包含 $i$ 的区间 $[L,R]$ ，只能存在一个位置有雌的，但是我们又钦定了这个位置是 $i$，所以 $j$ 一定不在任意一个包含 $i$ 的区间中，且小于所有满足条件的区间的 $L$ 的最小值，设这个值为 $minL$。

对于任意一个在 $i$ 前面且不包含 $i$ 的区间 $[L,R]$ 也必须有一个是雌的，所以我们只能让这个位置是 $j$ ，因此，$j$ 一定是在 $i$ 前面且不包含 $i$ 的区间 $[L,R]$ 中，且大于等于所有满足条件的区间的 $L$ 的最大值，设这个值为 $maxL$。

然后我们注意到 $minL$ 和 $maxL$ 是单增的，所以直接单调队列。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=2*1e5+10;
int _=1,n,m,dp[N],minL[N],maxL[N];
deque<int> q;
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n+1;i++) minL[i]=i;
		for(int i=1;i<=m;i++){
			int L,R;L=reads(),R=reads();
			minL[R]=min(minL[R],L);
			maxL[R+1]=max(maxL[R+1],L);
		}for(int i=n;i>=1;i--) minL[i]=min(minL[i],minL[i+1]);
		for(int j=1;j<=n+1;j++) maxL[j]=max(maxL[j],maxL[j-1]);
		for(int i=1;i<=n;i++) cout<<i<<":"<<minL[i]<<" "<<maxL[i]<<"\n";
		q.push_back(0);
		for(int i=1,j=1;i<=n+1;i++){
			for(;j<minL[i];j++){
				if(~dp[j]){
					while(!q.empty()&&dp[q.back()]<dp[j]) q.pop_back();
					q.push_back(j);
				}
			}while(!q.empty()&&q.front()<maxL[i]) q.pop_front();
			if(q.empty()) dp[i]=-1;
			else dp[i]=dp[q.front()]+(i!=n+1);
			cout<<i<<":"<<dp[i]<<"\n"; 
		}printf("%d\n",dp[n+1]);
	}return 0;
}

请注意，这是错解

前置知识：负环与差分约束。

我们把女生设为 $1$，男生设为 $0$，然后对序列求前缀和。条件就变成了 $s_r=s_{l-1}+1$。

然后由于原序列每一位都是 $0$ 或 $1$，所以前缀和序列中 $\forall i\in [1,n], s_{i-1}\le s_i\le s_{i-1}+1$。

我们根据这些不等关系进行差分约束。我们要找出答案的上界，所以我们把所有不等式转化成 $s_a\le s_b+c$ 的形式。

对于所有的 $s_a\le s_b+c$，在图中从 $b$ 到 $a$ 连一条边权为 $c$ 的边，使用 SPFA 跑最短路，如果出现负环则无解。

答案即为 $dis_n$。

时间复杂度 $\mathcal O(nm)$，但是使用优先队列替换普通队列后跑得飞快。

然后我们再加一个卡时，当快要 TLE 的时候输出 -1 并结束程序即可。

#include<bits/stdc++.h>
#define R(x) x=read()
#define int long long
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-') {
			y=-1;
		}
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=200005;
int n,m;
vector<pair<int,int> >G[N];
inline void add(int x,int y,int z) {
	G[x].push_back({y,z});
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int cnt[N],dis[N];
bool vis[N];
int tot;
inline int SPFA() {
	memset(dis,0x3f,sizeof dis),dis[0]=0;
	vis[0]=1;
	q.push({0,0});
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		vis[u]=0;
		for(auto pii:G[u]) {
			++tot;
			if(tot>20000000)return -1;    
			int v=pii.first,w=pii.second;
			if(dis[v]>dis[u]+w) {
				cnt[v]=cnt[u]+1;
				if(cnt[v]==n+1) return -1;
				dis[v]=dis[u]+w;
				if(!vis[v])vis[v]=1,q.push({dis[v],v});
			}
		}
	}
	return dis[n];
}
signed main() {
	R(n),R(m);
	for(int i=1; i<=n; ++i) {
		add(i,i-1,0),add(i-1,i,1);
	}
	for(int i=1,l,r; i<=m; ++i) {
		R(l),R(r);
		add(r,l-1,-1),add(l-1,r,1);
	}
	cout<<SPFA();
	return 0;
}