对于区间[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=υ 且满足 au−αv≥bu−bv ,则在图中加入一条从 u 指向 v 的有向边。
若顶点 V 能够沿着有向边可达区间内所有其他顶点,则称 V 是区间 [l,r] 上的一个 强势顶点 。特别地,如果区间内只有一个顶点,则该顶点也是强势顶点。对于每个查询,请输出该区间内强势顶点的个数。
【名词解释】