解题思路
问题分析
有向图构建规则
对于区间[l,r]内任意两个不同顶点u,v，如果满足条件a[u] - a[v] ≥ b[u] - b[v]，则在图中添加有向边u→v。
强势顶点定义
顶点V是强势顶点当且仅当V能够通过有向边到达区间内所有其他顶点。
P3363.第3题-区间强势顶点
题目内容
给定两个长度为 n 的整数数组 a 和 b ，下标从 1 到 n 。我们定义对于区间 [l,r] 上的有向图构造规则：
1. 顶点集合为区间内所有下标；
2. 若 u=υ 且满足 au−αv≥bu−bv ，则在图中加入一条从 u 指向 v 的有向边。
若顶点 V 能够沿着有向边可达区间内所有其他顶点，则称 V 是区间 [l,r] 上的一个 强势顶点 。特别地，如果区间内只有一个顶点，则该顶点也是强势顶点。对于每个查询，请输出该区间内强势顶点的个数。
【名词解释】
- 强势顶点：在有向图中，从该顶点出发，沿着边可以到达图中所有其他顶点的顶点。
输入描述
第一行输入两个整数 n(1≦n≦2×105) 和 q(1≦q≦2×105) ，分别表示数组长度和查询次数。
第二行输入 n 个整数 a1,a2,...,an(−105≦ai≦105) 。
第三行输入 n 个整数 b1,b2,...,bn(−105≦bi≦105) 。
接下来 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
说明
