M3532.针对图的路径存在性查询 I

思路：

• 由于 nums 单调不降排序，若 $r-l>1$，则 $l,r$ 间有边直接相连意味着 ${\text{nums}}_r-{\text{nums}}_l\le \text{maxDiff}\Rightarrow \mathrm{\forall }l\le i<r,{\text{nums}}_{i+1}-{\text{nums}}_i\le {\text{nums}}_r-{\text{nums}}_l\le \text{maxDiff}$，即边 $(i,i+1)$ 存在，$(l,r)$ 这条边可以被“替代”。
• 故只需考虑所有形如 $(i,i+1)$ 的边，进而可知对每个 $i$ 都有 ${\text{maxr}}_i$，表示从 $i$ 出发向右、能到达的最大节点编号。
• 回答询问时，不妨设 $u\le v$，则存在路径当且仅当 $v\le {\text{maxr}}_u$。

class Solution {
public:
	vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
		vector<int> maxr(n);
		vector<bool> answer;
		for (int i = 0; i < n; i++){
			int l = i;
			while (i + 1 < n && nums[i + 1] - nums[i] <= maxDiff) i++;
			for (int j = l; j <= i; j++){
				maxr[j] = i;
			}
		}
		for (vector<int> i : queries){
			if (i[0] > i[1]) swap(i[0], i[1]);
			answer.push_back(i[1] <= maxr[i[0]]);
		}
		return answer;
	}
};