解题思路

问题分析

有向图构建规则

对于区间[l,r]内任意两个不同顶点u,v，如果满足条件a[u] - a[v] ≥ b[u] - b[v]，则在图中添加有向边u→v。

强势顶点定义

顶点V是强势顶点当且仅当V能够通过有向边到达区间内所有其他顶点。

题目内容

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$ ，下标从 $1$ 到 $n$ 。我们定义对于区间 $[l,r]$ 上的有向图构造规则：

$1.$ 顶点集合为区间内所有下标； $2.$ 若 $u≠υ$ 且满足 $a_u-α_v ≥ b_u -b_v$ ，则在图中加入一条从 $u$ 指向 $v$ 的有向边。

若顶点 $V$ 能够沿着有向边可达区间内所有其他顶点，则称 $V$ 是区间 $[l,r]$ 上的一个 强势顶点 。特别地，如果区间内只有一个顶点，则该顶点也是强势顶点。对于每个查询，请输出该区间内强势顶点的个数。

【名词解释】

• 强势顶点：在有向图中，从该顶点出发，沿着边可以到达图中所有其他顶点的顶点。

输入描述

第一行输入两个整数 $n(1≦n≦2×10^5)$ 和 $q(1≦q≦ 2 × 10^5)$ ，分别表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^5≦a_i≦10^5)$ 。

第三行输入 $n$ 个整数 $b_1,b_2,...,b_n(-10^5≦b_i≦10^5)$ 。

接下来 $q$ 行，每行输入两个整数 $l$ 和 $r$ $(1≦l≦r≦n)$ ，表示一次区间查询。

输出描述

对于每个查询，输出一行一个整数，表示该区间内强势顶点的个数。

样例1

输入

5 3
1 3 2 5 4
2 1 4 3 0
1 5
2 4
3 3

输出

1
2
1

说明

在第一个样例中：

• 对区间 $[1,5]$ ，有唯一的强势顶点 $5$ ；

• 对区间 $[2,4]$ ，强势顶点为 $2,4$ ；

• 对区间 $[3,3]$ ，只有一个顶点 $3$ ，自然是强势顶点。

样例2

输入

6 2
1 1 1 1 1 1
2 2 2 2 2 2
1 6
4 6

输出

6
3

说明