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

Confused_Fhy · 2025-10-20 22:59:39 · 题解

区间覆盖板题。

题目描述

共有 n 条线段，每条线段可以涂 k 种颜色中一种，要求任意两条颜色相同的线段没有重合，求不同的涂色方案有多少种。

思路

显然，我们可以用一个优先队列维护每一条线段的左端点，找到前面有多少与它没有交集的线段，最后利用排列组合算出答案即可。
别忘了对传奇模数 998244353 取模。
别忘了清空优先队列。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rap(i, a, b) for(int i = a; i < b; i ++)
#define dwn(i, a, b) for(int i = a; i >= b; i --)
#define iosfst ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
const int mod = 998244353;
int pre[501000];
struct node{
    int l, r;
};
node a[501000];
bool cmp(node a, node b){
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}
priority_queue<int, vector<int>, greater<int>> q;
void solve(){
    int n, k; cin >> n >> k;
    rep(i, 1, n) cin >> a[i].l >> a[i].r;
    sort(a + 1, a + n + 1, cmp);
    int ans = 1;
    rep(i, 1, n){
        while(!q.empty() && q.top() < a[i].l) {
            k ++;
            q.pop();
        }
        ans *= k;
        ans %= mod;
        k --;
        q.push(a[i].r);
    }
    while(q.size()) q.pop();
    cout << ans << '\n';
}
signed main() {
    iosfst;
    int t; cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

STL 万岁。