专栏文章

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

GGeorgeDeng
P14239题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingcl74
此快照首次捕获于
2025/12/02 01:57
3 个月前
此快照最后确认于
2025/12/02 01:57
3 个月前
查看原文
容易想到小学一年级学的乘法原理：我们把之前和它有交的选段个数设为 gg，那么答案就要乘上 k−gk-g。
然后就很简单了。把线段按照左端点排序，用一个堆记录前面线段的右端点。显然，这个堆是一个小根堆。如果堆顶的右端点小于当前的左端点，那么与后面所有线段就肯定没有交了，可以直接 pop 掉。否则就把答案乘上 kk 减去堆里面的元素个数，然后把当前线段的右端点塞进去。注意取模。
单次时间复杂度 O(nlog⁡n)O(n\log n)。
AC 代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...