并查集

并查集是一种高效的数据结构,能够在接近O(1)的合并两个集合\查询两个元素是否在一个集合中.并查集在使用过程中还可以维护许多额外信息.

并查集用数组存储,存储为树的形式,一开始所有元素都自己单独形成一个并查集,当两个集合需要合并时就将之间某个集合的祖先结点指向另一个集合即可.

p[x]是x结点的祖先编号,祖先结点x的特征是p[x] = x;

初始化:

int p[N];  //节点
   for (int i = 1; i <= n; i++) {
        p[i] = i;//节点赋予编号
      //!开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数,一开始都是祖先结点
    }

在查询某两个集合是否在一个集合中是,使用如下定义的find函数:

inline int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
//上面 x:p[x]也可以是p[x]:p[x]

p[x]=find(p[x])会不断的套p[p[p[p[p[p[p[x....]]]]]]]相当于持续不断的访问父节点来寻找祖先,直到找到p[x]=x;

直到套很多层后p[p[p[p[p[…x]]]]] = x的时候回溯,回溯的时候由于有p[x] = find(p[x])这句,所以每一层的节点都会直接指向x,相当于把子节点到祖先结点的路径长度变为1, 下次再从这些子节点访问祖先结点只要O(1),这就是路径压缩.

合并集合:

p[find(a)] = find(b);//a的祖先的祖先(就是a祖先自己)是b的祖先. 合并了两个集合

判断两个元素是否在一个集合

 if (find(a) == find(b)) {//a的祖先等于b的祖先
        puts("Yes");
 } else {
        puts("No");
}

另:对于并查集集合性质的维护等价于在维护祖先结点的性质,例如集合中元素的数量,要以祖先结点为idx

例题

https://www.acwing.com/problem/content/242/

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1?N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D
表示说法的种类。 若 D=1，则表示 X 和 Y 是同类。 若 D=2，则表示 X 吃 Y。 输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3

本题可以维护一些集合,对于某种特定的动物x它对应了三个集合,设为x,x+n,x+n+n,表示的含义为x是同类域,x+n是捕食域,x+n+n是天敌域然后判断同类只要查询是否在一个集合,如果有a吃b的关系就把b与a+n合并,把b+n(b的捕食域)与a的天敌域(a+n+n)合并,把b+n+n(b的天敌域)与a的同类域(a)合并即可.

#include <iostream>
using namespace std;
const int N = 1e5 * 3;
int pt[N];
// x是同类域.
// x+n是捕食域
// x+n+n是天敌域
int ans;
int fa(int x) { return pt[x] == x ? pt[x] : pt[x] = fa(pt[x]); }
void merge(int x, int y) { pt[fa(x)] = fa(y); }
int main() {
    int n, k;
    cin >> n >> k;
    int a, b, p;
    for (int i = 1; i <= 3 * n; ++i) {//从1开始 从0开始也可以
        pt[i] = i;
    }

    for (int i = 0; i < k; ++i) {
        scanf("%d%d%d", &p, &a, &b);
        if (a > n || b > n) {
            ans++;
        } else if (p == 1) {//若是同类
        //!注意不能用反过来的条件判断 比如f(a)!=f(b) 不然有些真话无法插入进去 
            if (fa(a) == fa(b+n)||fa(a) == fa(b+n+n)) {//如果b吃a或a吃b 注意符号是||
                ans++;
            } else {
                merge(a, b);
                merge(a + n, b + n);
                merge(a + n + n, b + n + n);
            }
        } else {//若a吃b
            if (a==b||fa(a) == fa(b+n)||fa(a)==fa(b)) {//如果a,b是一个东西 或 a和b为同类 或 b吃a
                ans++;
            } else {
                merge(a + n, b);
                merge(a + n + n, b + n);
                merge(a, b + n + n);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

参考 https://www.acwing.com/solution/content/1007/

堆

堆是一颗完全二叉树,除了最底层之外其他层结点都是满的.这里我们取小根堆,有如下性质:

1.若k为某结点编号,其父结点编号为k/2,左子节点2k,右子节点2k+1

[HTML_REMOVED]

2.堆结点A若有子节点,则A的值小于(两个)子节点的值(若是大根堆就变成大于),两个子节点的值的大小不管

3.堆顶一定为堆中最小值(性质2的推论)

4.堆底层存满时时第二层元素为n/4个

堆的存储:

int heap[N], idx;

由于堆是一颗完全二叉树故可正好占满一个序列的位置,所以用数组存,idx代表用到点的个数.一般点要从1开始用(后文解释).

堆的一般操作:

1.down

down(t)代表把t元素下移,希望把t移到符合堆性质的位置.具体实现是比较t元素与其子节点值的大小(如果存在),假设存在a,b子节点,若t值小于a大于b则与t与a交换,若t值小于a小于b且b比a小则与b交换,这样逐渐向下直到字节点a’,b’的值都大于t为止.

t的值是堆中元素的下标.

void down(int k) {
    int t = k;
    if (2 * k <= idx && heap[2 * k] < heap[t]) t = 2 * k; //注意这里如果点从0开始用2*0还是0,不方便
    //!注意这里是heap[2 * k] < heap[t] 如果写成heap[2 * k] < heap[k] 就只跟k节点比大小了,没跟两个子节点没比大小
    if (2 * k + 1 <= idx && heap[2 * k + 1] < heap[t]) t = 2 * k + 1;
    if (t != k) {//t值不等于k值时,意味着可以交换/下移
        swap(heap[t], heap[k]);
        down(t);//由于是一颗完全二叉树,1e9的元素也不过三十层,所以直接递归
    }
}

2.up

up(t)代表把t元素上移,希望把t移到符合堆性质的位置.与down类似但相反,具体实现是比较t元素与其父节点值的大小(如果存在),若大于父节点值则交换,直到父节点值小于t/不存在父节点为止.

t的值是堆中元素的下标.

void up(int k) {
    while (k / 2 && heap[k / 2] > heap[k]) {
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}

[HTML_REMOVED]

3.建堆

建堆之前肯定是要输入元素的.注意点从1开始标号.

有一种O(n)的建堆方法:从所给数据的中点n/2开始向前遍历,遍历一个元素t就down(t).为什么是正确的?因为若从1开始标号,n/2正好是第二层结点,n/2元素右侧如果有结点是不需要down的,因为他们没有子结点而且是底层;又由于最后一层结点大小不管,只需要down包括n/2及前面的元素(可以手画一下),第二层元素(期望n/4个)最多down一次,第三层最多down两次,每层结点都是子节点数的1/2,有
$$ \frac{\mathrm{n}}{4}+2\cdot \frac{\mathrm{n}}{8}+3\cdot \frac{\mathrm{n}}{16}+\cdot \cdot \cdot +\left( \mathrm{n}-1 \right) \frac{\mathrm{n}}{2^{n+1}}\sim \mathrm{O}\left( \mathrm{n} \right) $$

for (int i = n / 2; i; i--) {
    down(i);
}

4.堆顶删除

先让堆顶heap[1] = heap[idx]堆尾,那么堆顶值就被删了,然后堆中此时有两个值为heap[idx]的元素,此时令idx–,那么堆尾元素就被删了,剩下原来堆顶元素的位置的值等于原堆尾,此时down(heap[1])即可.弹出堆顶等价于输出最小值,所以也相当于排序.

heap[1] = heap[idx];
idx--;
down(1);//down(t),t的值是堆中元素的下标.

例题:

https://www.acwing.com/problem/content/840/

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int heap[N], idx;
int a[N];
void down(int k) {
    int t = k;
    if (2 * k <= idx && heap[2 * k] < heap[t]) t = 2 * k;  
    //!注意这里是heap[2 * k] < heap[t] 如果写成heap[2 * k] < heap[k] 就只跟k节点比大小了,没跟两个子节点没比大小
    if (2 * k + 1 <= idx && heap[2 * k + 1] < heap[t]) t = 2 * k + 1;
    if (t != k) {
        swap(heap[t], heap[k]);
        down(t);//由于是一颗完全二叉树,1e9的元素也不过三十层,所以直接递归
    }
}
void up(int k) {
    while (k / 2 && heap[k / 2] > heap[k]) {
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    idx = n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", heap + i);
    }
    for (int i = n / 2; i; i--) {
        down(i);
    }
    for (int i = 0; i < m; ++i) {
        printf("%d ", heap[1]);
        heap[1] = heap[idx];
        idx--;
        down(1);
    }
    return 0;
}

堆的进阶版

先看例题,按例题分析

https://www.acwing.com/problem/content/242/

维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6

//题目要求任意位置删除,修改.

1.存储

进阶版的堆支持修改删除任意元素(这里指按输入顺序的任意第k个点).为了能够达到这个条件,需要保存输入时堆中元素的位置,也能够根据堆中元素位置找到插入的顺序.

int heap[N];  //堆
int ph[N];    //存放第k个插入点的在堆中的下标
int hp[N];    //存放堆中i点的插入次序
int idx;      // idx 记录的是堆当前的数据多少

用了两个表达意义互为反函数的两个数组ph和hp

2.swap函数

由于up和down操作需要交换元素,那么对应点的ph和hp值也需要交换,因此要升级swap函数,同样的在up\down函数中的swap要变成升级后的swap函数.

void heap_swap(int a, int b) {
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
}

这里a,b为堆中下标,令k1,k2为a,b的插入次序,则k1=hp[a],k2=hp[b],交换堆中的值就是swap(heap[a],heap[b]),两个点相互交换那么一开始插入的顺序也要交换,即为swap(hp[a],hp[b]),按插入顺序的第k1,k2个点在堆中的下标也要交换,即swap(ph[k1],ph[k2])~swap(ph[hp[a]],ph[hp[b]]).这三条语句的顺序可以变,因为相对独立.

[HTML_REMOVED]

3.堆顶删除

heap_swap(1, idx);
idx--;
down(1);//没变化,和普通堆一样

4.插入堆尾操作

插入的时候按照上文就要记录插入的数的次序m,也是总共插入的数.(和idx不一样,idx是数据个数,删除了元素就比m小)

由于插入的时堆尾只需要up即可.m要++,要先更新ph,hp再up,因为一旦up里面就要交换,但交换的时候找不到ph[m]和hp[idx],所以要先更新ph,hp再up(idx).

scanf("%d", &x);
m++;
heap[++idx] = x;//堆尾
ph[m] = idx;
hp[idx] = m;
up(idx);

5.删除插入的第k个元素

删除插入顺序的第k个点与堆顶删除类似,让heap[ph[k]] = heap[idx]对吗? 不对,因为删除元素要更新ph和hp,所以用堆交换heap_swap(ph[k],idx), 令idx–,那么堆尾元素就被删了,然后down(?) down什么呢?down接收堆中元素的下标也就是ph[k],而这里ph[k]是交换后k点在堆中元素的下标,因为ph[k]在上一句heap_swap的时候已经被更改了,所以要用临时变量保存ph[k]

由于元素要么down要么up 干脆都执行(要意识到堆尾不一定是最大值,最大值存在于最后一层,如果删除的元素所在的子树的元素都很大,那么原堆尾是有可能up然后去另外一颗子树)

scanf("%d", &k);
int u = ph[k];  //这里一定要用u=ph[k]保存第k个插入点的下标
heap_swap(u, idx);  //因为在此处heap_swap操作后ph[k]的值已经发生
idx--;  //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
down(u);
up(u);

6.修改插入的第k个元素

直接修改值然后down,up就行.

scanf("%d%d", &k, &x);
heap[ph[k]] =
x;  //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
up(ph[k]);
down(ph[k]);  //所以可直接传入ph[k]作为参数

代码:

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int heap[N];  //堆
int ph[N];    //存放第k个插入点的下标
int hp[N];    //存放堆中点的插入次序
int idx;      // size 记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
// h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int a, int b) {
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
}
void down(int u) {
    int t = u;
    if (u * 2 <= idx && heap[t] > heap[u * 2]) t = u * 2;
    if (u * 2 + 1 <= idx && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;
    if (u != t) {
        heap_swap(u, t);
        down(t);
    }
}
void up(int u) {
    if (u / 2 > 0 && heap[u] < heap[u / 2]) {
        heap_swap(u, u / 2);  //!不能写heap[u] heap[u/2]
        up(u >> 1);
    }
}
int main() {
    int n;
    cin >> n;

    int m = 0;  // !! 一定记得初始化本地变量!!!!
    //      m用来记录插入的数的个数
    //注意m的意义与idx是不同的 idx是记录堆中当前数据的多少
    //对应上文 m即是hp中应该存的值
    while (n--) {
        char op[5];
        int k, x;
        cin >> op;
        if (op[0] == 'I') {
            scanf("%d", &x);
            m++;
            heap[++idx] = x;
            ph[m] = idx;
            hp[idx] = m;
            up(idx);
        } else if (op[0] == 'P')
            printf("%d\n", heap[1]);
        else if (op[0] == 'D' && op[1] == 'M') {
            heap_swap(1, idx);
            idx--;
            down(1);
        } else if (op[0] == 'D') {
            scanf("%d", &k);
            int u = ph[k];  //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u, idx);  //因为在此处heap_swap操作后ph[k]的值已经发生
            idx--;  //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(u);
            up(u);

        } else {
            scanf("%d%d", &k, &x);
            heap[ph[k]] =
                x;  //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            up(ph[k]);
            down(ph[k]);  //所以可直接传入ph[k]作为参数
        }
    }
    return 0;
}