D. Rescue Nibel!

转化题意
就是叫我们求k条线段都有重合的方案数
最开始想的是离散化+线段树
手模拟一下样例这样会是有重复的
我们要如何保证不重不漏！
显然我们可以将线段排序
然后当前线段和前面线段相交有几条（我们一定要选这条）然后再组合数一下就可以了
然后我们因为相交我们只用check前面的r端点是否大于等于我们该线段l
这个可以用什么 没错就是 单点修改 区间查询的树状数组！
然后注意的就是组合数的板子必须x>y啊啊啊

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int tr[N<<1],n,k;
vector<int>v;
int a[N],b[N];
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    return a[x]%mod*b[y]%mod*b[x-y]%mod;
}
int lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    for(int i=x;i<=6e5+10;i+=lowbit(i))(tr[i]+=c)%=mod;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))(res+=tr[i])%=mod;
    return res;
}
int find(int x){
    return lower_bound(all(v),x)-v.begin();
}
void upd(int l,int r,int x){ //区间修改用
    add(l,x),add(r+1,-x);
}
int que(int l,int r){ //区间ch
    return (query(r) - query(l-1)+mod)%mod;
}
void solve() {
    cin>>n>>k;
    vector<int>l(n),r(n);
    v.push_back(0);
    vector<pair<int,int>>seg;
    for(int i=0;i<n;i++){
        cin>>l[i]>>r[i];
        v.push_back(l[i]),v.push_back(r[i]);
        seg.emplace_back(l[i],r[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    sort(all(seg));
    int ans=0;
    for(int i=0;i<n;i++){
        auto [z,y]=seg[i];
        int t=(que(find(z),6e5)+mod)%mod;
        if(t>=k-1)(ans+=C(t,k-1))%=mod;
        add(find(y),1);
    }
    cout<<ans<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    a[0]=b[0]=1;
    for(int i=1;i<=3e5;i++){
        a[i]=(a[i-1]*i)%mod;
        b[i]=b[i-1]*qmi(i,mod-2,mod)%mod;
    }
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

原文地址：http://www.cnblogs.com/ycllz/p/16835789.html