题意：有 \(n\) 个讲师，对于讲师 \(i\)，他可以在 \([l_i,r_i]\) 中选一天讲课，问对于 \(x \in [1,n]\)，有多少连续的 \(x\) 天可以做到都有讲师讲课。
先考虑区间的 \(l\) 互不相同时如何解决。
对于已知的 \([l,r]\) 是否存在完美匹配，判断是简单的，我们贪心地按天数从左往右依次解决，每次填覆盖当前天的 \(r\) 最小的讲师即可。
根据 hall 定理，我们发现若 \([l,r]\) 满足条件，那么 \([nl,nr] \subseteq [l,r]\) 必然满足条件，所以我们只需要判断 \([l,r]\) 是否满足条件即可。
然后我们从后往前扫求对于第 \(i\) 天，符合条件的最大的 \(R_i\) 在哪里就行了，这个根据上面的贪心处理即可。
那么对于区间 \(l\) 有相同的其实差不多，若区间 \([l,r]\) 被分配给了第 \(d\) 天，那这个区间可以被写成 \([d,r]\)，然后就和区间的 \(l\) 互不相同的时候一样了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e9,N=2e5+5;
int n,m;
vector<int> ed[N];
multiset<int> s;
int c[N],nc[N],op[N],pos[N],res[N];
signed main(){
n=read();
for(int i=1;i<=n;i++){
int l=read(),r=read();
ed[l].push_back(r);
m=max(m,r);
}
for(int i=1;i<=m;i++){
for(auto r:ed[i]) s.insert(r);
while(s.size()&&*s.begin()<i) s.erase(s.begin());
if(s.size()){
int r=*s.begin();
s.erase(s.begin());
c[i]++,c[r+1]--;
op[i]=1;
}
else nc[i]++;
}
for(int i=1;i<=m;i++) nc[i]+=nc[i-1],c[i]+=c[i-1];
int r=m+1;
for(int i=m;i>=1;i--){
int num=c[i]-op[i]+1+nc[i-1];
pos[nc[i]]=i;
if(num<=m&&pos[num]) r=min(r,pos[num]);
res[r-i]++;
}
for(int i=n;i;i--) res[i]+=res[i+1];
for(int i=1;i<=n;i++) cout<<res[i]<<'\n';
}