题目大意是给出若干盏灯, 每个灯会先在某个时间打开, 之后在某个时间关闭. 打开和关闭的时刻会在题目输入中给出. 求问: 如果从这些灯中选取 \(k\)盏, 存在多少种不同的选取方式使得存在某个时刻这 \(k\) 盏灯全是亮的. 题目的数据特点: 灯开关的时刻可能的变化范围远远大于灯的数量, 以至于无法对时刻进行枚举.

(这部分也是看了 CF 给的 editorial 才明白的, 感觉这种离散化的方法才是最值得学习的)

时刻的取值范围过大, 但是实际上由于灯的数量相对较少, 实际上不同的时刻数量很少. 因此我们可以考虑进行某种离散化的操作. 用 editorial 里面的说法这叫做 event method. 普通的离散化在这个问题上的困难之处在于如果分开成两个数组, 就难以区分时间先后顺序了. 这里假设某盏灯打开的时间时 \(l\), 关闭的时间是 \(r\). 那么直接将 \(2*l, 2*r+1\), 插入同一个数组. 这样通过对数组的排序自然就让不同事件按发生先后顺序排列, 同时也可以通过奇偶性判断事件的类型.

假设此时有 \(a\) 盏灯打开, 在下一个事件发生的时刻同时有 \(b\) 盏灯打开, 则因为这 \(b\) 盏灯打开而新增的选取方法数目为

\[ {a+b\choose k} - {a\choose k} \]

这样按照事件枚举即可.

下面是一份 AC 的 C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

#include <cstring>

#include <stdint.h>

using namespace std;

inline void io_speed_up()
{
        cin.tie(nullptr);
        cin.sync_with_stdio(false);
        cout.tie(nullptr);
}

#ifndef ONLINE_JUDGE
#define TRACE
#endif
#ifdef TRACE
#define trace(...) __trace__(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __trace__(const char *name, Arg1 &&arg1)
{
        cout << "[#]";
        cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __trace__(const char *names, Arg1 &&arg1, Args &&... args)
{
        cout << "[#]";
        const char *comma = strchr(names + 1, ',');
        cout.write(names, comma - names) << " : " << arg1 << " | ";
        __trace__(comma + 1, args...);
}
#else
#define trace(...) ;
#endif

const int64_t MAXN = (int64_t)3e5 + 5;

const int64_t INF = (int64_t)1e9 + 7;

const int64_t MOD = 998244353;

inline int64_t fast_pow(int64_t a, int n)
{
        int64_t ans = 1;
        while (n)
        {
                if (n & 1)
                {
                        ans = ans * a % MOD;
                }
                n >>= 1;
                a = a * a % MOD;
        }
        return ans;
}

inline int64_t inverse(int a)
{
        return fast_pow(a, MOD - 2);
}

int64_t factorial[MAXN];
int64_t factorial_inverse[MAXN];

inline int64_t comb(int n, int k)
{
        if (k > n)
        {
                return 0;
        }
        return (factorial[n] * factorial_inverse[k] % MOD) * factorial_inverse[n - k] % MOD;
}

int main()
{
        io_speed_up();

        int n, k;
        cin >> n >> k;
        factorial[0] = 1;
        factorial_inverse[0] = inverse(1);
        int64_t last = 1;
        for (int i = 1; i < n + 5; ++i)
        {
                factorial[i] = last * i % MOD;
                last = factorial[i];
                factorial_inverse[i] = inverse(last);
        }
        trace("?");
        int events[MAXN * 2];
        for (int i = 0; i < n; ++i)
        {
                int l, r;
                cin >> l >> r;
                events[i] = l << 1;
                events[i + n] = r << 1 | 1;
        }
        sort(events, events + 2 * n);
        int64_t ans = 0;
        int current_on = 0;
        int change = 0;
        int i = 0;
        int j;
        for (; i < 2 * n; i = j)
        {
                j = i;
                while (events[i] == events[j] && j < 2 * n)
                {
                        j += 1;
                }
                change = j - i;

                if (events[i] & 1)
                {
                        // close lamp
                        current_on -= change;
                }
                else
                {
                        // open lamp
                        ans += comb(current_on + change, k);
                        ans += MOD - comb(current_on, k);
                        ans %= MOD;
                        current_on += change;
                }
        }
        cout << ans << endl;
        trace(ans);

        return 0;
}