智乃的k线段区间

在数轴上有$N$条线段，第$i$条线段的左右端点分别为$l_i,r_i$。

定义一段区间$[L,R]$包含第$i$条线段，当且仅当$L\le l_i\le r_i\le R$。

智乃想要知道$L,R\in [1,M]$且$L\le R$时，有多少个区间$[L,R]$包含至少$K$条线段。

输入：
第一行输入三个正整数$N,M,K(1\le K\le N\le 10^5,1\le M\le 10^9)$。
接下来$N$行，每行输入两个正整数$l_i,r_i(1\le l_i\le r_i\le M)$。

输出：
仅一行一个非负整数，表示问题的答案。

样例1：
输入

6 9 3 3 5 4 6 5 7 8 8 8 8 8 8

6 9 3
3 5
4 6
5 7
8 8
8 8
8 8```

输出
--

 19

思路：我们先预处理出所有“包含K条线段”的最小区间。这一步预处理过程我们可以借助std::priority_queue，然后就可以选择这k条线段左右两边的所有点进行乘法原理，然后考虑某些区间可能会重复，那么我们右边区间每次只选一部分。

代码：`#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl ‘\n’
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;

bool cmp(pii x, pii y){
return x.second < y.second;
}

void solve(){
int n, m, k;
cin >> n >> m >> k;
vectora(n + 1);
for(int i = 1;i <= n;i ++){
cin >> a[i].first >> a[i].second;
}
int ans = 0;
sort(a.begin(), a.end(), cmp);
priority_queue<int,vector,greater>q;
for(int i = 1;i <= n;i ++){
int e;
if(i == n){
e = m - a[i].second + 1;
}else{
e = a[i + 1].second - a[i].second;
}
q.push(a[i].first);
while(q.size() > k)
q.pop();
if(q.size() == k)
ans += q.top() * e;
}
cout << ans << endl;
}

signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t = 1;
while(t–)
{
solve();
}
return 0;
}
`