1008. 病毒片段

题目描述

随着网络攻击手段的演变，新型计算机病毒往往具有复杂的变体结构。为了应对这一威胁，某网络安全实验室构建了一个庞大的病毒特征库。库中包含了 $n$ 个已知的病毒代码特征片段，每个片段在内存地址空间中可视为一段连续的区间 $[l_i, r_i]$，代表该病毒特征出现的内存起止位置。

为了提高检测效率，实验室开发了一款新型的「区间扫描引擎」。该引擎并不对整个内存进行全量扫描，而是针对可疑的内存区域进行定向分析。

现在，引擎接收到了 $q$ 次扫描任务。每次任务给出一个待检测的内存区间 $[L, R]$。为了确保检测的准确性，引擎需要在特征库中寻找一条特征片段 $j$，满足以下条件：

1. 该特征片段必须完全包含在待检测区间内，即 $L \le l_j$ 且 $r_j \le R$。
2. 在所有满足条件 1 的特征片段中，选择长度最长的一个。定义一个片段的长度为 $r_j - l_j + 1$。

对于每次扫描任务，请输出能够匹配到的最长特征片段的长度。如果在该区域内没有任何完整的特征片段，则判定为安全，输出 $0$。

输入格式

第一行输入一个整数 T ($1\le T \le 20$)，表示数据组数。

对于每组数据，第一行包含两个整数 $n, q$（$1 \le n, q \le 2 \times 10^5$），分别表示特征库中特征片段的数量和扫描任务的次数。

接下来 $n$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le 10^9$），表示第 $i$ 个特征片段的内存区间。

接下来 $q$ 行，每行包含两个整数 $L, R$（$1 \le L \le R \le 10^9$），表示一次扫描任务的待检测区间。

输出格式

对于每次询问，输出一行一个整数，表示在区间 $[L, R]$ 内完全包含的最长特征片段的长度。若不存在，输出 $0$。

样例输入

1
5 3
1 5
2 4
3 3
6 8
7 10
1 5
2 6
7 12

样例输出

5
3
4

提示

询问 $[1, 5]$：

• 片段 1 ($[1, 5]$) 满足 $1 \le 1$ 且 $5 \le 5$，包含在内。
• 片段 2 ($[2, 4]$) 满足 $1 \le 2$ 且 $4 \le 5$，包含在内。
• 片段 3 ($[3, 3]$) 满足 $1 \le 3$ 且 $3 \le 5$，包含在内。
• 最长长度为 $\max(5, 3, 1) = 5$。

询问 $[2, 6]$：

• 片段 1 ($[1, 5]$) 不满足，因为 $l_1=1 < L=2$。
• 片段 2 ($[2, 4]$) 满足，长度 3。
• 片段 3 ($[3, 3]$) 满足，长度 1。
• 片段 4 ($[6, 8]$) 不满足，因为 $r_4=8 > R=6$。
• 最长长度为 $3$。

询问 $[7, 12]$：

• 片段 5 ($[7, 10]$) 满足，长度 4。
• 最长长度为 $4$。

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1008