飞船调度 题目描述 Gold Ship 在玩一款太空即时战略游戏。游戏中有 $n$ 支舰队，每支舰队中可以包含若干飞船，每艘飞船都有一个正整数等级。 游戏开始时，所有舰队都是空的。接下来需要依次执行 $q$ 次操作，操作共有六种： 1. 造船 1 x v：建造一艘等级为 $v$ 的飞船，并加入第 $x$ 支舰队。 2. 训练 2 x v：将第 $x$ 支舰队中所有飞船的等级都增加 $v$。 3. 移动 3 x y：将第 $x$ 支舰队中一艘中位数等级的飞船移动到第 $y$ 支舰队。如果第 $x$ 支舰队为空，则该操作没有效果；如果中位数等级的飞船不止一艘，移动其中任意一艘。 4. 查询 4 x：询问第 $x$ 支舰队中飞船等级的中位数。如果第 $x$ 支舰队为空，答案为 $0$。 5. 合并 5 x y：将第 $x$ 支舰队中的所有飞船转移到第 $y$ 支舰队中，第 $x$ 支舰队变为空。 6. 删除 6 x v：删除第 $x$ 支舰队中所有等级不超过 $v$ 的飞船。 对于一支含有 $k$ 艘飞船的舰队，将所有飞船等级从小到大排序后，位于第 $\left\lceil \frac{k}{2} \right\rceil$ 个位置的数定义为该舰队的中位数。例如，序列 $1,1,2,3,4$ 的中位数是 $2$，序列 $4,6,7,10$ 的中位数是 $6$。 输入格式 第一行包含两个正整数 $n,q$，分别表示舰队数量和操作次数。 接下来 $q$ 行，每行描述一次操作，格式为以下六种之一： 1 x v 2 x v 3 x y 4 x 5 x y 6 x v 输出格式 对于每个查询操作，输出一行一个整数，表示查询结果。其他操作不输出任何信息。 数据范围 所有测试点满足 $1 \le n,q \le 400000$。 所有操作中出现的参数 $x,y$ 满足 $1 \le x,y \le n$，参数 $v$ 满足 $1 \le v \le 10^7$。 保证移动和合并操作中 $x \ne y$。 子任务约束如下： Subtask 1：$n,q \le 2000$。 Subtask 2：没有训练和合并操作。 Subtask 3：无特殊限制。 输入样例 3 12 1 1 4 1 1 4 1 2 1 1 2 3 2 2 2 3 2 1 3 3 2 4 1 1 3 3 5 1 3 6 3 3 4 3 输出样例 4 4 样例说明 前四次操作后，第 $1$ 支舰队有等级 $4,4$ 的飞船，第 $2$ 支舰队有等级 $1,3$ 的飞船。 第 $5$ 次操作后，第 $2$ 支舰队变为 $3,5$。 第 $6$ 次操作移动第 $2$ 支舰队的一艘中位数等级飞船后，第 $1$ 支舰队包含 $3,4,4$，第 $2$ 支舰队包含 $5$。 第 $7$ 次操作因第 $3$ 支舰队为空而没有效果。 第 $8$ 次操作查询第 $1$ 支舰队，中位数为 $4$。 第 $9$ 次操作后，第 $3$ 支舰队包含 $3$。 第 $10$ 次操作后，第 $1$ 支舰队清空，第 $3$ 支舰队包含 $3,3,4,4$。 第 $11$ 次操作后，第 $3$ 支舰队删除所有等级不超过 $3$ 的飞船，剩下 $4,4$。 第 $12$ 次操作查询第 $3$ 支舰队，中位数为 $4$。