经典二分查找

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

题目内容

小蓝正在处理两个整数序列 $X$ 和 $Y$，他希望从序列 $X$ 中选一个元素 $x$，从序列 $Y$ 中选一个元素 $y$，使得它们的绝对差 $|x - y|$ 落在给定的闭区间 $[l, r]$ 内。请你帮他统计一共有多少种不同的选择方案。

两个序列的长度均不超过 $10^5$，序列中的元素均为正整数且不超过 $10^9$。$l$ 和 $r$ 满足 $0 \le l \le r \le 10^9$。

输入描述

第一行包含两个整数 $N$ 和 $M$，分别表示序列 $X$ 和 $Y$ 的长度。 第二行包含 $N$ 个整数，表示序列 $X$。 第三行包含 $M$ 个整数，表示序列 $Y$。 第四行包含两个整数 $l$ 和 $r$，表示允许的绝对差范围。

输出描述

输出一个整数，表示满足条件的配对数量。

样例1

输入

2 2
1 5
2 6
1 2

输出

2

说明

序列 $X = [1, 5]$，序列 $Y = [2, 6]$，允许的绝对差区间为 $[l, r] = [1, 2]$。

依次检查所有配对：

• $|1 - 2| = 1$，落在 $[1, 2]$ 内，计数 1；
• $|1 - 6| = 5$，不在区间内；
• $|5 - 2| = 3$，不在区间内；
• $|5 - 6| = 1$，落在 $[1, 2]$ 内，计数 1。

总计满足条件的配对数为 2。

样例2

输入

3 3
1 2 3
2 3 4
0 0

输出

2

说明

序列 $X = [1, 2, 3]$，$Y = [2, 3, 4]$，$l = r = 0$，要求绝对差为 $0$，即 $x$ 与 $y$ 必须相等。

检查所有配对：

• $1$ 与 $Y$ 中任意元素均不相等；
• $2$ 与 $Y$ 中的 2 相等，满足 $|2 - 2| = 0$，计数 1；
• $3$ 与 $Y$ 中的 3 相等，计数 1；
• 其余配对均不相等。

共计 2 种选择方案。

样例3

输入

2 2
10 20
100 200
50 80

输出

1

说明

序列 $X = [10, 20]$，$Y = [100, 200]$，区间 $[50, 80]$。

逐个计算绝对差：

• $|10 - 100| = 90$，不在区间内；
• $|10 - 200| = 190$，不在区间内；
• $|20 - 100| = 80$，恰好在区间内，计数 1；
• $|20 - 200| = 180$，不在区间内。

满足条件的配对仅有 $(20, 100)$ 一组，答案为 1。