区间并查集|树状数组

lc3245

lc3244

区间并查集 _并边

i = set.find(i + 1))
set.merge(i, q[1]-1);

这步实现跳跃

class UFS
{
public:
vector<int> fa;
int size;

UFS(int n)
{
fa.resize(n);
iota(fa.begin(), fa.end(), 0);
size = n;
}

int find(int x)
{
if (x >= fa.size()) return fa.size();
if(fa[x]!=x) {
fa[x]=find(fa[x]);
}
return fa[x];
}

bool merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx == fy) return false;
fa[fx] = fy;
size--;
return true;
}
};

class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
UFS set(n - 1);
vector<int> ans;
for (auto& q : queries)
{
for (int i =q[0]; i < q[1];i = set.find(i + 1))
set.merge(i, q[1]-1);

ans.push_back(set.size);
}
return ans;
}
};