二分+并查集

lcp62

lc3532

并查集+二分，直接输入数组原地并查集

并查集管理数组索引，merge(j, j + 1);//数值差≤maxDiff的相邻索引合并，到同一集合，查询时判断if (find(u) == find(v)) //两个索引是否在同一集合，返回各查询的连通性结果

其实就是判断u是否可以扩散到v，可扩散到 find自然等

class Solution {
public:
vector<int> pa;
int find(int x)
return pa[x] == x ? x : pa[x] = find(pa[x]);

voidmerge(int u, int v)
pa[find(u)] = find(v);

vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries)

{
pa.resize(n);
iota(pa.begin(), pa.end(), 0);

for (int i = 0; i < nums.size(); i++) {
int idx = upper_bound(nums.begin(), nums.end(), nums[i] + maxDiff) - nums.begin();
for (int j = find(i); j < idx - 1; j = find(j))
merge(j, j + 1);//数值差≤maxDiff的相邻索引合并，到同一集合
}

vector<bool> ans(queries.size(), false);
for (int i = 0; i < queries.size(); i++) {
int u = queries[i][0], v = queries[i][1];
if (find(u) == find(v)) //两个索引是否在同一集合
ans[i] = true;
}
return ans;
}
};