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

· · 题解

简单题。

思路

感觉与廊桥分配很相似啊。

首先把所有区间的左端点从小到大排序，然后依次考虑对每个线段进行染色。不难发现，如果我们知道当前线段能够被染成多少种颜色，则乘法原理连乘起来就是答案。

于是变成了个非常典的区间覆盖问题，即有多少个区间覆盖了当前区间的左端点，只需要把对应区间的右端点丢进优先队列里去维护即可，时间复杂度 O(Tn\log n)。

代码

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=5e5+10;
const ll MOD=998244353;
ll n,k;
pair<ll,ll> dt[N];
void solve(){
    cin>>n>>k;for(ll i=1;i<=n;i++) cin>>dt[i].first>>dt[i].second;
    sort(dt+1,dt+1+n);ll ans=1;
    priority_queue<ll,vector<ll>,greater<ll> > qu;
    for(ll i=1;i<=n;i++){
        while(!qu.empty()&&qu.top()<dt[i].first){k++;qu.pop();}
        ans=ans*k%MOD;k--;qu.push(dt[i].second);
    } 
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll T;cin>>T;while(T--) solve();
    return 0;
}