5315 - 第二十四章 双指针和莫队:莫队回滚(难)
时间限制 : 3 秒
内存限制 : 52 MB
给出长为 n 的序列 a,第 i 个元素是一个区间 [l_i,r_i]。
m 次询问,给出 A,B,求出 a 中最长的区间(即这个序列中的一段),使得这个区间内每个区间都与 [A,B] 有交集。输出这个最长区间的长度。
输入
第一行两个整数 n,m。
接下来 n 行,第 i 行两个整数 l_i,r_i。
接下来 m 行,每行两个整数 A,B,为一次询问。
输出
输出 m 行,每行一个整数,为询问的答案。
样例
输入
3 3 2 5 1 3 6 6 3 5 1 10 7 9
输出
2 3 0
提示
1\le n\le 5\times 10^4,1\le m\le 2\times 10^5,1\le l_i\le r_i\le 10^9,1\le A\le B\le 10^9