DAY 2 并查集
训练情况简介
今天的讲题准备的不是很充分哈
下次注意！！！
6.28补：
22级厉害学弟整理的简单构造的题解
早上
21级今天训练并查集
后面找时间补吧
A B 并查集裸题
C题目前没有明白怎么解，或者说与并查集的关系？
C题看下题解吧呜呜呜，有点整不明白了
下午
先找了C题的题解，。。。好像早上其实已经理解七八分了
题解：把这m个点看成m个边，(a,b)看成a到b的一条边。转化后发现，当一些点在同一个圈中，则它们需要额外一次的移动。可以这么求解最优解：默认是m次移动，每增加一个圈，需要增加一次移动；每多一些不需移动的点(x,x)，则减少一次移动。
K题
暴力差分数组过不去，正好学一学树状数组
利用树状数组维护差分数组，实现数据的区间修改和单点查询
那么，并查集怎么做呢？
就是利用并查集的思想，数据范围较大，暴力解会超时。但是我们发现一个数换成它的数位和的话，同一个数即使很大，操作次数也是很小的，并且在变成只有个位数之后不需要我们再进行操作了。如 999999999->81->9。所以我们在每次进行更新操作的时候，我们立即对a数组进行更新，如果说\(a_i\)在这时已经是个位数了，那么我们将\(a_i\)的父亲指向\(a_{i+1}\)，那么下次遍历的时候，给定的l，我们都从x=ds.findfa(l)开始，当\(x<r\)的时候，继续遍历，\(x=findfa(x+1)\)，直至结束。
很溜的并查集思想，用来去掉无用数据！！！
晚上开始喽~
G题第一眼，和并查集有关？
看了洛谷的题解，和自己的想法有点像？但是我不会multiset，所以现学了multiset，就是一个可以插入重复元素的set
也看到了并查集的做法，只不过这里的不像之前看到的并查集，这里更像指针？
并查集写完了，就是一个暴力的指针，类似于并查集路径缩短的思路来快速找到满足条件的数
L题dij模板题，但是不知道哪里写错了之前，debug了30分钟。。。
M题题意没读懂，或者说读懂了不会做？
就是要我求所有可达路径的边的最大跳跃距离的最小？（应该没错）
其实，就是说，所有路径的最大跳跃距离的最小，需要遍历每个石头，将每个石头作为跳板，判断其他石头以这个石头作为跳板的最大值，存下最大值，遍历途中不断取最大的最小即可
遍历结束后即可得到结果。
可以再好好理解一下！
title摘记
https://vjudge.net/contest/565340
下面是总结的，总结部分题给大家添加到下方了，大家也可以按照总结进行刷题，后面几题可能较为简单，添加的题目绝大部分不大于CF1900难度。其中有力扣的题还是很不错的，大家也可以去力扣刷刷题，这里一些是并查集扩展用法可以好好学一学
普通并查集
可视化 https://visualgo.net/zh/ufds
https://oi-wiki.org/ds/dsu/
https://cp-algorithms.com/data_structures/disjoint_set_union.html
并查集时间复杂度证明 https://oi-wiki.org/ds/dsu-complexity/
RMQ 标准算法和线性树上并查集 https://ljt12138.blog.uoj.ac/blog/4874
模板题 https://www.luogu.com.cn/problem/P3367 (已做)
https://atcoder.jp/contests/arc097/tasks/arc097_b (已做)
基础题 https://codeforces.com/problemset/problem/1411/C (已做)
LC305 https://leetcode.cn/problems/number-of-islands-ii/
LC1562 https://leetcode.cn/problems/find-latest-group-of-size-m/
处理图上的环
https://codeforces.com/contest/1726/problem/D
数组标记/区间合并相关
1851. 包含每个查询的最小区间
2382. 删除操作后的最大子段和
2334. 元素值大于变化阈值的子数组
2612. 最少翻转操作数
https://codeforces.com/problemset/problem/724/D
https://codeforces.com/problemset/problem/827/A
https://codeforces.com/problemset/problem/1157/E
树+点权顺序
LC2421 https://leetcode.cn/problems/number-of-good-paths/
贡献法 https://codeforces.com/problemset/problem/915/F
LC2503 https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/
接水问题 https://codeforces.com/problemset/problem/371/D
三维接雨水 https://www.luogu.com.cn/problem/P5930 LC407 https://leetcode-cn.com/problems/trapping-rain-water-ii/
使某些点不在环上需要删除的最少边数 https://ac.nowcoder.com/acm/contest/7780/C
todo https://codeforces.com/problemset/problem/292/D
任意合并+区间合并 https://codeforces.com/problemset/problem/566/D
动态加点 https://codeforces.com/contest/1494/problem/D
思维转换 https://nanti.jisuanke.com/t/43488
https://codeforces.com/problemset/problem/1012/B
https://codeforces.com/problemset/problem/1466/F
前缀和 后缀和 https://codeforces.com/problemset/problem/292/D
维护树或基环树 https://codeforces.com/problemset/problem/859/E
求矩阵的 rank 矩阵 https://codeforces.com/problemset/problem/650/C LC1632 https://leetcode-cn.com/problems/rank-transform-of-a-matrix/submissions/
分组排序套路 LC1998 https://leetcode-cn.com/problems/gcd-sort-of-an-array/
套题 https://blog.csdn.net/weixin_43914593/article/details/104108049 算法竞赛专题解析（3）：并查集
转换 https://codeforces.com/problemset/problem/1253/D
离散 + 四方向 Kick Start 2019 Round C Wiggle Walk https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ff2/0000000000150aac#analysis
技巧：去掉无用数据
https://codeforces.com/problemset/problem/1157/E (已做)
https://codeforces.com/problemset/problem/1791/F (已做)