牛客周赛 Round 166
小月的长廊官方中文
题目描述
官方中文小月正在探索一款冒险游戏中的魔法长廊。长廊可以看作一条数轴，其上共有 $n$ 个结界，编号依次为 $1,2,\dots,n$。第 $i$ 个结界覆盖闭区间 $[l_i,r_i]$，包括左右两个端点。 对于数轴上的任意位置 $x$，定义 $\operatorname{d}(x)$ 为覆盖该位置的结界数量，即满足 $l_j \leqq x \leqq r_j$ 的结界 $j$ 的数量。所有结界同时存在，即使多个结界的覆盖范围完全相同，也分别计数。 给定一个整数 $p$，小月想知道，有多少个结界的左右端点覆盖次数之差的绝对值不小于 $p$。也就是说，请统计满足 $|\operatorname{d}(l_i)-\operatorname{d}(r_i)| \geqq p$ 的结界数量。官方中文
输入格式
官方中文第一行输入两个整数 $n,p\left(1 \leqq n \leqq 2 \times 10^5;\ 0 \leqq p \leqq n\right)$，表示结界数量、覆盖次数之差的绝对值下限。
此后 $n$ 行，第 $i$ 行输入两个整数 $l_i,r_i\left(1 \leqq l_i \leqq r_i \leqq 10^9\right)$，表示第 $i$ 个结界覆盖区间的左右端点。官方中文
输出格式
官方中文输出一个整数，表示满足 $|\operatorname{d}(l_i)-\operatorname{d}(r_i)| \geqq p$ 的结界数量。官方中文
样例
Input #1
5 2
1 5
2 5
5 8
3 7
5 6Output #1
4各结界的端点覆盖次数如下：
$\hspace{23pt}\bullet\,$第 $1$ 个结界：$\operatorname{d}(1)=1$，$\operatorname{d}(5)=5$，差的绝对值为 $4$；
$\hspace{23pt}\bullet\,$第 $2$ 个结界：$\operatorname{d}(2)=2$，$\operatorname{d}(5)=5$，差的绝对值为 $3$；
$\hspace{23pt}\bullet\,$第 $3$ 个结界：$\operatorname{d}(5)=5$，$\operatorname{d}(8)=1$，差的绝对值为 $4$；
$\hspace{23pt}\bullet\,$第 $4$ 个结界：$\operatorname{d}(3)=3$，$\operatorname{d}(7)=2$，差的绝对值为 $1$；
$\hspace{23pt}\bullet\,$第 $5$ 个结界：$\operatorname{d}(5)=5$，$\operatorname{d}(6)=3$，差的绝对值为 $2$。
除第 $4$ 个结界外，其余结界均满足条件，因此答案为 $4$。
Input #2
5 1
1 2
2 3
3 4
4 5
5 6Output #2
2由于结界包含左右端点，位置 $2$、$3$、$4$、$5$ 均被两个结界覆盖，位置 $1$、$6$ 均只被一个结界覆盖。仅第 $1$ 个和第 $5$ 个结界满足条件，因此答案为 $2$。
题目信息
题面与样例版权归 牛客竞赛 及出题人所有；中文翻译由 AI 生成（官方原文），如有出入请以原文为准。