[AdditionalFile4230.zip](file://AdditionalFile4230.zip?type=additional_file)

#4230. 「ROI 2021 Day2」砍树

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2021 Day2 T3. Вырубка деревьев

2D 组织负责发放森林砍伐许可证。他们收到了一些沿公路砍伐树木的申请。公路上有 $n$ 棵树，第 $i$ 棵树位于坐标 $x_i$ 处，高度为 $h_i$。树木的信息按坐标顺序排列，即 $x_1 < x_2 < \ldots < x_{n-1} < x_n$。

树木可以按以下方式逐一砍伐。树木从根部砍倒，然后必须向左或向右倒下。为了避免树木在倒下时受损，它不能碰到距离小于其高度的其他未砍伐的树木。换句话说，如果位于 $x_i$ 处、高度为 $h_i$ 的树木向右倒下，则在 $x_i < x_j < x_i + h_i$ 范围内不应有未砍伐的树木。如果这棵树向左倒下，则在 $x_i - h_i < x_j < x_i$ 范围内不应有未砍伐的树木。

在 $x_1$ 处的树木左侧和 $x_n$ 处的树木右侧有重要建筑物，因此禁止将树木倒在 $[x_1, x_n]$ 范围之外。换句话说，位于 $x_i$ 处、高度为 $h_i$ 的树木不能向左倒下，如果 $x_i - h_i < x_1$，也不能向右倒下，如果 $x_i + h_i > x_n$。

组织收到 $q$ 份砍伐树木的申请。每个申请由两个数字 $l_i$ 和 $r_i$ 表示，意味着申请人希望砍伐编号从 $l_i$ 到 $r_i$ 的树木。

在执行申请的过程中，只允许砍伐编号从 $l_i$ 到 $r_i$ 的树木。被砍倒的树木可以倒向编号 $l_i$ 左侧或编号 $r_i$ 右侧的区域，但不能超出区间 $[x_1, x_n]$。不允许碰到编号不在 $l_i$ 到 $r_i$ 范围内的树木。

对于每个申请，需要计算在不损坏任何树木的情况下，可以砍伐的最大树木数量。每个申请应独立处理。

输入格式

第一行包含两个整数 $n, q\ (1 \leq n, q \leq 5\cdot 10^5)$，表示树木数量和申请数量。

接下来的 $n$ 行，每行包含两个整数 $x_i, h_i\ (1 \leq x_i \leq 10^9, 1 \leq h_i \leq 10^9)$，描述每棵树的位置和高度。保证 $x_1 < x_2 < \ldots < x_n$。

接下来是 $q$ 行，每行包含两个整数 $l_i, r_i\ (1 \leq l_i \leq r_i \leq n)$，表示申请砍伐的树木编号范围。

输出格式

对于每个申请，输出在不损坏任何树木的情况下可以砍伐的最大树木数量。

样例 1

输入

3 3
1 3
3 1
4 2
1 1
2 3
1 3

输出

0
2
3

样例 2

输入

5 3
1 5
3 1
4 2
5 3
6 1
1 5
5 5
1 1

输出

5
1
0

样例 3

输入

1 1
100 100
1 1

输出

0

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

在第 $7$ 个子任务中，有 $30$ 个测试点，每个测试点单独评分，分值为 $1$。只有在通过前六个子任务的所有测试点后，才会对这些测试点进行评分。