acm-(区间交,贪心,multiset,排序,思维)Codeforces Round #672 (Div. 2) D.Rescue Nibel!

传送门

考虑将所有区间按照左端点由小到大排序，然后按这个顺序来枚举区间并进行check，对于当前区间而言，考虑在它之前的区间中能否挑出k-1个区间使得它们与当前区间都至少有一个公共交点。由于之前的区间的左端点都是小于等于当前区间的左端点，因此只要保证它们的右端点大于等于当前区间左端点那么就一定与当前区间存在交集，也就是符合条件的区间。

那么如何获得满足该条件(即右端点大于等于当前区间左端点)区间的个数呢，考虑使用multiset来解决该问题，我们每次check完一个区间后，就将该区间的右端点加入multiset，因此multiset存的一定是之前区间的右端点，由于每次check的区间的左端点单调不减，因此对于multiset中小于当前左端点的值我们都可以erase掉，毕竟这个右端点以后不可能对后面左端点更大的区间作出任何贡献了。于是multiset中维护的都一定是符合条件(右端点值大于等于当前区间左端点值)的区间，假设数量是 s i z e \mathbf{size} size，那么只需要从这些区间中选取的方案有 C s i z e k − 1 \mathbf{C_{size}^{k-1}} Csizek−1​个。

将check每个区间得到的值累加即是总方案数。

const ll mod = 998244353;
ll fac[maxn],fav[maxn];
struct Node{
	int l,r;
	bool operator <(const Node b)const{
		return l<b.l;
	}
}a[maxn];
void init(int n){
	fac[0]=1;
	FOR(i,1,n+1)fac[i]=fac[i-1]*i%mod;
	fav[n]=qpow(fac[n],mod-2,mod);
	ROF(i,n-1,0)fav[i]=fav[i+1]*(i+1)%mod;
}
ll C(int a,int b){
	if(a<b)return 0;
	return fac[a]*fav[b]%mod*fav[a-b]%mod;
}
multiset<int>s;
int main(){
	init(maxn-1);
	int n,k;
	rd(&n,&k);
	FOR(i,0,n)rd(&a[i].l,&a[i].r);
	sort(a,a+n);
	ll ans=0;
	FOR(i,0,n){
		while(!s.empty() && *s.begin()<a[i].l)s.erase(s.begin());
		ans=(ans+C((int)s.size(),k-1))%mod;
		s.insert(a[i].r);
	}
	wrn(ans);
}