数据结构

数据结构

并查集

功能

并查集维护了一些不相交的集合，支持两种操作：

查询（Find）：查询两个元素是否在同一个集合中。
合并（Union）：把两个不相交的集合合并为一个集合。

初始化

并查集的结构是一个森林，其中每棵树表示一个集合，根节点作为集合的代表元素。

每个节点只存储它的父节点，根节点的父节点指向自己。

digraph G {
0;
1;
2;
3;
4;
5;
0->0 ;
1->1 ;
2->2 ;
3->3 ;
4->4 ;
5->5 ;
}

struct dsu {
  vector<int> fa;
  dsu(int n) : fa(n) { iota(fa.begin(), fa.end(), 0); }
};

合并

只需要将一个集合的根节点指向另一个集合的根节点即可。

合并 1 号节点的集合和 2 号节点的集合：

digraph G {
rankdir=BT;
0;
1;
2;
3;
4;
5;
0->0 ;
1->1 ;
2->1 ;
3->3 ;
4->4 ;
5->5 ;
}

合并 1 号节点的集合和 3 号节点的集合：

digraph G {
rankdir=BT;
0;
1;
2;
3;
4;
5;
0->0 ;
1->3 ;
2->1 ;
3->3 ;
4->4 ;
5->5 ;
}

启发式合并

我们可以将节点较少或深度较小的树（通常是节点数较少的树）连到另一棵树上，避免树退化成链。

按秩合并：

bool unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) {
    return false;
  }
  if (sz[x] < sz[y]) {
    swap(x, y);
  }
  fa[y] = x;
  sz[x] += sz[y];
  // sum[x] += sum[y];
  return true;
}

查询

查询两个元素是否在同一个集合中，只需要看它们的根节点是否相同即可。

路径压缩

查询过程中遇到的节点可以直接指向根节点，方便后续查询。

例如在下面的并查集中查询 4 号节点

digraph G {
rankdir=BT;
0;
1;
2;
3;
4;
5;
0->0 ;
1->3 ;
2->1 ;
3->3 ;
4->2 ;
5->2 ;
}

把经过的 1 2 4 号节点直接接在 3 号节点上

digraph G {
rankdir=BT;
0;
1;
2;
3;
4;
5;
0->0 ;
1->3 ;
2->3 ;
3->3 ;
4->3 ;
5->2 ;
}

路径压缩会在一次查询中改变多个节点，因此在可持久化并查集等修改代价较高的情况下通常只使用按秩合并。

删除 & 移动

为了保证删除节点时不会影响到其他节点，我们只能删除叶子节点。

我们可以预先为每个节点分配一个虚拟节点作为父亲。

这样就可以保证所有实际的节点都是叶节点，删除或移动时直接修改即可。

完整代码

struct dsu {
  vector<int> fa, sz;
  // vector<ll> sum;
  dsu(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); }

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

  bool same(int x, int y) { return find(x) == find(y); }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
      return false;
    }
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    fa[y] = x;
    sz[x] += sz[y];
    // sum[x] += sum[y];
    return true;
  }
};

时间复杂度

按秩合并与路径压缩都没有：最坏
只有按秩合并：
只有路径压缩：平均，最坏
路径压缩 + 启发式合并：

例题

P3367【模板】并查集

模版题

P1197【JSOI2008】星球大战

给定一张图，依次删除一些点，求每次删除后的联通块数量。

离线，求出最终的状态，将删除的节点按相反顺序依次加入图中，并查集维护联通块数量。

P2024【NOI2001】食物链

有三类动物，吃，吃，吃。

现有个动物，以编号。每个动物都是中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示和是同类。
第二种说法是 2 X Y，表示吃。

依次给出个句话，当一句话与之前的真话矛盾时（即不存在分配动物种类的方案满足这些描述），这句话就是假话，否则就是真话。

输出假话的总数。

做法 1

对每种动物建 3 个点，表示它自己、它的天敌、它的猎物。

对于“ 和是同类”的描述，把对应的自己、天敌、猎物并起来

对于“ 吃 ”的描述，并天敌，猎物并，天敌并猎物。

如果两个动物已经有关系并且和给定的描述矛盾，则说明是假话。

做法 2

使用带边权的并查集，边权为两个动物的关系。

资料

https://oi-wiki.org/ds/dsu/

https://zhuanlan.zhihu.com/p/93647900

单调队列

功能

单调队列实现了这样的功能：

像普通队列一样入队、出队。
查询队列内元素的最大值（或最小值）。

例题

P1886 滑动窗口 /【模板】单调队列

有一个长为的序列，以及一个大小为的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

资料

https://oi-wiki.org/ds/monotonous-queue/

st 表

P3865 【模板】ST 表 && RMQ 问题

板子题

P3793 由乃救爷爷

板子题（静态数组多次询问区间最大值），但数据范围大一点

分块，每块大小，块间建 st表，块内维护前缀后缀最值，可以完成预处理。

块间查询拆成后缀+整块+前缀，复杂度

块内暴力，复杂度

可以使用位运算优化块内查询：

对于区间，可以将查询看成有一个单调队列，先将入队，再将出队，然后查询单调队列队首。

对于每个，用一个整数记录依次入队后每个数是否在单调队列中，查询时将对应的整数左移位，再查 lowbit 得到最值的位置。

cp数据结构

Contents