【扫描线+计数去重】Codeforces Round #672 (Div. 2) D. Rescue Nibel!

题目链接：

https://codeforces.com/contest/1420/problem/D

题意：

有n个灯泡，他们开关的时间分别为 l[i] 和 r[i]，在某一时刻，选择k个亮着的灯泡，求能取的方案数

思路

1. 一开始的想法是用离散化来做，考虑每一个时刻有多少个灯泡是亮着的，然后利用组合数学来算
2. 但是我们会发现，这种情况会重复，如图，红线的两种情况，都需要判断一下，但是其中124这种情况会被计数两次，所以就要找一种方式使得计数的时候不重
   
3. 一般处理计数重复的问题有两种方法，容斥和 选择取和不取分类讨论
4. 于是我们就可以发现，我们单独考虑一个区间，我们会发现，最终的答案=取它的答案+不取它的答案，所以我们在原来扫描线的基础上，我们直接来考虑取的这种情况，因为我们会发现，从左向右扫过去，如果说当前位置已经被扫过，那么剩下没有计算的答案就是它没有被扫过的情况，而没有扫过的情况是有其他所有的点被扫过的总和
5. 所以我们计算的时候只需要计算一下扫过去的过程中对于每一个区间的结尾，当前时刻能否取k个并且包括该区间

代码

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<stack>
#include<math.h>
#define INF 0x3f3f3f3f
#define MAXN 2010

using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double PI=acos(-1);
const int maxn=1e6+100;
const int inf=0x7fffffff;
#define N maxn
int t,n,k;
int l[maxn],r[maxn],num[maxn];
P node[maxn];
const ll mo=998244353;
ll C(ll n,ll m){
    static ll M=0,inv[N],mul[N],invMul[N];
    while(M<=n){
        if(M){
            inv[M]=M==1?1:(mo-mo/M)*inv[mo%M]%mo;
            mul[M]=mul[M-1]*M%mo;
            invMul[M]=invMul[M-1]*inv[M]%mo;
        }
        else mul[M]=1,invMul[M]=1;
        M++;
    }
    return mul[n]*invMul[m]%mo*invMul[n-m]%mo;
}

int main()
{
   scanf("%d%d",&n,&k);
   int cnt=0;
   for(int i=1;i<=n;i++)
   {
     scanf("%d%d",&l[i],&r[i]);
     node[++cnt]=P(l[i],0);
     node[++cnt]=P(r[i],1);
   }
   sort(node+1,node+1+cnt);
   ll num=0,ans=0;
   for(int i=1;i<=cnt;i++)
   {
       if(node[i].second==0) num++;//计数，计算当前有几个灯泡亮了
       else
       {
           //在一个区间的末尾，计算对于当前时刻来说，取该区间时可以取k个的方案数
           if(num-1>=k-1)ans=(ans+C(num-1,k-1))%mo;
           num--;
       }
   }
   cout<<ans<<endl;
   return 0;
}