AcWing 5267. 合格数
原题链接
中等
作者:
风入松-forest
,
2023-10-01 13:28:39
,
所有人可见
,
阅读 63
题目描述
- 给定$n$个整数区间,其中第$i$个区间为$[l_i,r_i]$。如果一个整数被至少$k$个给定区间所包含,就称这个整数为合格数。你需要回答$q$个问题。第i个问题给定两个整数$a,b$,请你计算$[a,b]$范围内有多少个合格数。
输入格式
- 第一行包含三个整数$n,k,q$。接下来$n$行,每行包含两个整数$l_i,r_i$,表示一个给定区间。接下来$q$行,每行包含两个整数$a,b$,用来描述一个问题。
输出格式
- 每个问题输出一行结果,一个整数,表示$[a,b]$范围内合格数的数量。
数据范围
- 前4个测试点满足$1≤k≤n≤5$,$1≤q≤5$。所有测试点满足$1≤k≤n≤2×10^5$,$1≤q≤2×10^5$,$1≤l_i≤r_i≤2×10^5$,$1≤a≤b≤2×10^5$。
样例
输入
3 2 4
1 4
2 7
7 9
2 4
3 7
5 6
1 10
输出
3
3
0
4
算法
算法类型
时间复杂度
算法分析
- 本题主要利用
差分
和前缀和
这两个算法完成对合格数的统计。
- 具体思路如下:
- 首先设置差分数组
b
和前缀和数组s
。
- 本题主要利用
b
数组记录各个数被包含的区间数(这一步主要用于后续判断某数是否满足至少被包含在k个区间内)。
- 利用条件
k
来进一步进行筛选。满足区间数大于等于k
的,将对应的b[i]
置为1
,否则置为0
。(这一步为后续求前缀和做准备)
s
数组为前缀和数组,s[i]
表示1-i
中合格数的数目。(这一步为后续在时间复杂度为O(1)
的情况下完成对区间内数量的统计做准备)
- 完成对
q
次查询的合格数数量统计。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, k, q;
int l[N], r[N]; //存放给定整数区间的左右两端
int b[N]; // 差分数组
int s[N]; // 前缀和数组
int A, B; //存放查询区间的左右两端
void insert(int l, int r, int c) //差分的模板函数
{
b[l] += c;
b[r + 1] -= c;
return;
}
int main()
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
insert(l[i], r[i], 1);
}
for (int i = 1; i < N; i++)
{
b[i] = b[i - 1] + b[i];
}
for (int i = 1; i < N; i++)
{
if (b[i] >= k)
{
b[i] = 1;
}
else
{
b[i] = 0;
}
}
for (int i = 1; i < N; i++)
{
s[i] = s[i - 1] + b[i];
}
for (int i = 1; i <= q; i++)
{
cin >> A >> B;
cout << s[B] - s[A - 1] << endl;
}
return 0;
}