D. Rescue Nibel!
题意
给出n<1e5个区间[Li,Ri] ,(Li,Ri<1e9)
要求找到k个区间他们有公共点
问有多少组区间 (每组k个)满足要求
题解
有关区间统计问题 想到差分前缀 按端点排序 和离散化
我们定义P(x)为覆盖x点的区间有多少个
定义S(x)为以x为起点的区间有多少个
由于区间端点值的范围较大而区间个数很小 可以离散化左右端点
然后对于每个区间的端点值Li处 Psum[Li]++ , Ri处Psum[Ri+1]–;
对Psum求前缀和 那么对于Psum[i] 就相当于覆盖i点的区间有多少个
对于S(x)可以在离散化后直接统计记为Cnt[i]
那么以一个点x作为起始点 求有多少组区间可以满足他们的公共点包括x
那么对于这个点对答案产生的贡献=C(Psum[x],k)-C(Psum[x]-Cnt[x],k)
减去C(Psum[x]-Cnt[x],k)是因为
统计的标准是以x作为起始点有多少组区间可以满足他们的公共点包括x
那么Psum[x]-Cnt[x]个区间虽然在x处有公共点但是不以x为起始点
它们会在以y,(y<x)为起始点时被统计入答案 所以要减去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=6e5+5;
const int Mod=998244353;
ll fac[Max],inv[Max];
int Psum[Max],Cnt[Max];
struct Seg{int L,R;}seg[Max];
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=ans*x%Mod;
x=x*x%Mod;y>>=1;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=Max;i++)fac[i]=fac[i-1]*i%Mod;
inv[Max]=qpow(fac[Max],Mod-2);
for(int i=Max-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%Mod;
}
ll C(int n,int m){return n>=m?fac[n]*inv[m]%Mod*inv[n-m]%Mod:0;}
vector<int>data;
int main() {
Turnoff;
ll ans=0;init();
int n,k;cin>>n>>k;
for(int i=0;i<n;i++){
int L,R;cin>>L>>R;
seg[i]={L,R};
data.push_back(L);
data.push_back(R);
}
sort(data.begin(),data.end());
data.erase(unique(data.begin(),data.end()),data.end());
for(int i=0;i<n;i++){
seg[i].L=lower_bound(data.begin(),data.end(),seg[i].L)-data.begin();
seg[i].R=lower_bound(data.begin(),data.end(),seg[i].R)-data.begin();
Cnt[seg[i].L]++;Psum[seg[i].L]++,Psum[seg[i].R+1]--;
}
int len=data.size();
for(int i=1;i<len;i++)Psum[i]+=Psum[i-1];
for(int i=0;i<len;i++){
ans=(Mod+ans+C(Psum[i],k)-C(Psum[i]-Cnt[i],k))%Mod;
}
cout<<ans<<endl;
}
|