[CF1965F] conference
題意：有 \(n\) 個講師，對于講師 \(i\)，他可以在 \([l_i,r_i]\) 中選一天講課，問對于 \(x \in [1,n]\)，有多少連續的 \(x\) 天可以做到都有講師講課。
先考慮區間的 \(l\) 互不相同時如何解決。
對于已知的 \([l,r]\) 是否存在完美匹配，判斷是簡單的，我們貪心地按天數從左往右依次解決，每次填覆蓋當前天的 \(r\) 最小的講師即可。
根據 hall 定理，我們發現若 \([l,r]\) 不滿足條件，那么 \([l+1,r]\) 和 \([l,r-1]\) 必然也不滿足條件。所以對于從第 \(i\) 天開始，符合條件的右端點 \(R_i\) 是單調不降的。
所以我們從后往前掃求對于第 \(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';
}
浙公網安備 33010602011771號