题目描述
给定一个包含 n 个点的序列,第 i 个点的坐标为 (ai,bi) 。
共有 q 次询问,每次询问一个区间 [l,r] ,你需要求出下面式子的值。
min
保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。
输入格式
第一行输入两个正整数 n, q 。
接下来 n 行,每行输入两个整数 a_i, b_i ,表示第 i 个点的坐标为 (a_i, b_i) 。
接下来 q 行,每行输入两个正整数 l, r ,表示询问区间 [l, r] 。
输出格式
输出 q 行,每行包含一个非负整数,表示答案。
样例一输入
4 5 1 1 2 2 1 2 2 1 1 4 1 3 1 2 2 3 3 4
样例一输出
1 1 2 1 2
样例二
见下发文件下的 geo2.in
与 geo2.ans
。
该样例约束与测试点 2 一致。
样例三
见下发文件下的 geo3.in
与 geo3.ans
。
该样例约束与测试点 18 一致。
下发文件
本题下发的文件除三个样例外还有 rand.cpp
。
rand.cpp
是一个数据生成器,与生成评测用例的数据生成器仅有随机种子不同。
输入 n, q, A, B 后数据生成器才可生成整个数据,数据输出到 geo.in
,其中 A, B 分别表示 |a_i| 与 |b_i| 的上界。
数据范围
对于所有测试点, 2 \le n \le 10^6 , 1 \le q \le 10^6 , |a_i|, |b_i| \le 10^9 , 1 \le l < r \le n ,保证 a_i, b_i, l, r 在指定范围内用指定方式随机生成。
测试点表格
测试点编号 | n \le | q \le |
---|---|---|
1 \sim 2 | 2 \times 10^3 | 2 \times 10^3 |
3 \sim 8 | 2 \times 10^4 | 2 \times 10^4 |
9 \sim 14 | 2 \times 10^5 | 2 \times 10^5 |
15 \sim 16 | 2 \times 10^3 | 10^6 |
17 \sim 19 | 10^6 | 10 |
20 \sim 25 | 10^6 | 10^6 |
对于每一档部分分,设其测试点编号范围为 l \sim r ,则测试点 l+1 \sim r-1 满足 |a_i|, |b_i| \le 10^6 ,测试点 \lfloor \frac{l+r}{2} \rfloor + 1 \sim r 满足 b_i = 0 。
提示
本题输入输出规模较大,请使用较为快速的输入输出方式。