题解：P14239 [CCPC 2024 Shandong I] 多彩的线段 2

· · 题解

容易想到小学一年级学的乘法原理：我们把之前和它有交的选段个数设为 g，那么答案就要乘上 k-g。

然后就很简单了。把线段按照左端点排序，用一个堆记录前面线段的右端点。显然，这个堆是一个小根堆。如果堆顶的右端点小于当前的左端点，那么与后面所有线段就肯定没有交了，可以直接 pop 掉。否则就把答案乘上 k 减去堆里面的元素个数，然后把当前线段的右端点塞进去。注意取模。

单次时间复杂度 O(n\log n)。

AC 代码：

#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

int n,k;
struct node{
    int l,r;
}a[500005];
bool cmp(node a,node b){
    return a.l<b.l;
}
priority_queue<int,vector<int>,greater<int>  > q;
void solution(){
    cin>>n>>k;
    while(!q.empty()) q.pop();
    for(int i = 1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+1+n,cmp);//按照左端点排序
    int ans = 1;
    int now = k;//处理k-g的值
    for(int i = 1;i<=n;i++){
        while(!q.empty()&&q.top()<a[i].l){
            q.pop();
            now++;//g -1了，now自然要+1
        }
        ans*=now;
        now--;//在把自己减掉
        ans%=998244353;//取模！
        q.push(a[i].r);
    }
    cout<<ans<<endl;
}
signed main()
{
    int _;
    cin>>_;
    while(_--){
        solution();
    }
    return 0;
}