CF1420D Rescue Nibel (貪心+思維)

連結

題意：

有 條線段 ，你需要從中選出 條令他們的交集不為空，求方案數對

分析：

/// 欲戴皇冠，必承其重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef unsigned long long ull;

#define x first
#define y second
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define debug(x) cout << #x <<": " << x << endl;

const int MOD = 998244353;
const int mod = 998244353;
const int N = 6e5 + 10;
const int dx[] = {0, 1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 0, 1, -1};
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll n, m;
ll fac[N],infac[N];
struct node 
{
    ll l,r;
}q[N];
bool cmp(node a,node b){
    if(a.l!=b.l)
    return a.l<b.l;
    return a.r<b.r;
}
ll qpow(ll a, ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
ll a[N],b[N];
ll num;
void add(ll x){
    while(x<=num){
        b[x]++;
        x+=lowbit(x);        
    }    
}
ll ask(ll x){
    ll ans=0;
    while(x){
        ans+=b[x];
        x-=lowbit(x);
    }
    return ans;
}
ll C(ll x,ll y){
    return fac[x]*infac[y]%mod*infac[x-y]%mod;
}
void solve(){    
    scanf("%lld%lld",&n,&m);
    ll ans=0;
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=n;i++) infac[i]=qpow(fac[i],mod-2);
    for(int i =1;i<=n;i++){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        a[++num]=q[i].l;
        a[++num]=q[i].r;
    }
    sort(q+1,q+1+n,cmp);
    sort(a+1,a+1+num);
    num=unique(a+1,a+1+num)-a-1;
    for(int i=1;i<=n;i++){
        q[i].l=lower_bound(a+1,a+1+num,q[i].l)-a;
        q[i].r=lower_bound(a+1,a+1+num,q[i].r)-a;
        ll cnt = ask(num)-ask(q[i].l-1);//ll cnt = (i-1)-ask(q[i].l-1);
        add(q[i].r);
        if(cnt>=m-1){
            ans=(ans+C(cnt,m-1))%mod;
        }        
    }
    printf("%lld\n",ans);
}
int main()
{
    ll t = 1;
    //scanf("%lld", &t);
    while(t--)
    {
        solve();
    }
    return 0;
}