一、题目要求
有N种颜色的小球，开始同一种颜色小球装在同一个筐里面，颜色从1到N标号。有下面两个操作(Cab)，把颜色是b的球所在筐中的球都倒进颜色是a的球所在的筐。(Qc)，查询颜色是c的球所在的筐中，哪种颜色的球最多，哪种颜色的球最少，输出球的个数
输入格式
第一行两个正整数N、M。M表示一共有M个操作。(1<=N、M<=100000)。第二行是N个由空格隔开的正整数，第i个数表示颜色为i的球有ai个，ai在int范围内。接下来的M行，对应M个操作。
输出格式
对于每个查询输出一行，每行两个正整数，第一个为最大值，第二个为最小值。
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
样例一input
6 6 1 2 3 4 5 6 C 1 2 C 3 4 C 5 6 C 1 3 C 1 5 Q 1
outout：
6 1
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
二、设计思路
设计基于并查集数据结构，用以高效处理“合并”和“查询”操作。
数据结构设计
- 并查集（Union-Find）结构：主要用于管理和追踪每种颜色球的归属，每个筐通过一个领导者（即并查集中的根节点）来标识。
- parent 数组：用于表示每个节点的父节点，若 parent[x] == x，则 x 是根节点。
- size 数组：记录每个根节点所代表的集合的大小，用于在合并时优化树的高度，以保持树的平衡，从而加速查询操作。
- colorCount 向量：这是一个向量，其中的每个元素都是一个哈希表（unordered_map），用于存储该根节点集合中不同颜色球的数量。
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
功能实现
1.初始化：
- 使用 initialCount 数组初始化 colorCount，这个数组记录了每种颜色球的初始数量。
- 初始时，每种颜色的球自成一组，其根节点即其自身，且每个筐只包含一种颜色的球。
2.合并操作（unionSet）：
- 查找两个颜色所在集合的根节点。
- 如果根节点不同，将一个集合合并到另一个集合。为了保持树的平衡，通常将较小的集合合并到较大的集合中（基于 size 数组）。
- 更新根节点的 colorCount 哈希表，将被合并集合的颜色球数量加到目标集合的对应颜色上。
3.查询操作（query）：
- 查找指定颜色所在的集合的根节点。
- 遍历根节点的 colorCount 哈希表，找到数量最多和最少的球，输出这两个值。
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
性能优化
- 路径压缩：在查找操作中使用路径压缩技术，使得每个节点直接或间接指向根节点，减少后续查找的深度。
- 按秩合并：通过比较集合的大小（利用 size 数组），总是将较小的集合合并到较大的集合，这有助于保持并查集树的平衡，提高效率。
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
三、代码展示
#include <iostream> #include <vector> #include <unordered_map> using namespace std; struct UnionFind { vector<int> parent; vector<int> size; // 代码略....>👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈 // 代码略.... // 代码略.... int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (size[rootX] < size[rootY]) { swap(rootX, rootY); } parent[rootY] = rootX; size[rootX] += size[rootY]; for (auto& p : colorCount[rootY]) { colorCount[rootX][p.first] += p.second; } } } // 代码略.... // 代码略.... // 代码略.... }; int main() { // 代码略.... >👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈 // 代码略.... // 代码略.... int N, M; cin >> N >> M; vector<int> initialCount(N); for (int i = 0; i < N; ++i) { cin >> initialCount[i]; } // 代码略.... // 代码略.... // 代码略.... return 0; }
运行结果：
👉👉👉 源码获取 关注【测试开发自动化】公众号，回复 “ 归类查询” 获取。👈👈👈
