公司（company）- 清华大学

一家初创企业共有 n 名员工，员工编号从 1 到 n。每位员工 i 拥有一个确定的薪资值 a_i。

初始状态下，所有员工均不了解其他同事的薪资情况。由于一次数据库故障，共泄露了 m 条信息，导致部分员工获知了其他员工的薪资数据。

对于员工 i，若其得知若干名员工的薪资，记其所了解人员的平均薪资为 v_i（重复获取的信息也计入平均值计算），当满足条件 a_i < v_i 时，该员工将产生离职倾向。

若某员工未获取任何他人薪资信息，则不会产生离职想法。

现给出所有员工的薪资数组 a_i，以及 m 组数据对 (x_i, y_i)，表示员工 x_i 获悉了员工 y_i 的薪资。请计算最终有多少员工会产生离职的想法。

输入格式

• 第一行输入两个正整数 n 和 m，分别代表公司总人数与泄露的数据条数。
• 第二行包含 n 个正整数，依次为每个员工的薪资 a_i。
• 接下来 m 行，每行包含两个正整数 x_i 和 y_i，表示员工 x_i 知晓了员工 y_i 的薪资。

数据范围

所有测试数据满足：

• 3 ≤ n ≤ 10
• 1 ≤ m ≤ 2 × 10
• 1 ≤ a_i ≤ 10
• 1 ≤ x_i, y_i ≤ n

输出格式

输出一个整数，表示产生离职想法的员工总数。

4 4
10 20 30 40
3 2
3 4
3 4
1 2

2

飞船调度 - 清华大学

Gold Ship 正在进行一款太空即时战略游戏。游戏中存在 n 支舰队，每支舰队可容纳多艘飞船，每艘飞船具有一个等级（正整数）。

初始时，所有舰队均为空。玩家将执行 q 次操作，类型包括以下六种：

1. 造船：给定参数 x, v，建造一艘等级为 v 的飞船，并将其加入第 x 支舰队。
2. 训练：给定参数 x, v，使第 x 支舰队中所有飞船的等级提升 v 点。
3. 移动：给定参数 x, y，将第 x 支舰队中任意一艘最低等级的飞船移动至第 y 支舰队。若该舰队为空，则无变化；若有多个同等级最低飞船，则任选其一移动。
4. 查询：给定参数 x，返回第 x 支舰队中飞船等级的中位数。若舰队为空，则返回 0。
5. 合并：给定参数 x, y，将第 x 支舰队的所有飞船全部转移至第 y 支舰队，原第 x 支舰队清空。
6. 删除：给定参数 x, v，移除第 x 支舰队中所有等级不超过 v 的飞船。

对于一支包含 k 艘飞船的舰队，其中位数定义为：将所有飞船等级按升序排列后，取第 k/2 个位置的数值。例如：

• 序列 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 ≤ n, q ≤ 400000
• 操作中的参数 x, y 满足 1 ≤ x, y ≤ n
• 参数 v 满足 1 ≤ v ≤ 10
• 在“移动”与“合并”操作中，保证 x ≠ y

子任务 1（20 分）：n, q ≤ 2000

约束条件：n 和 q 的值均不超过 2000，即 n, q ≤ 2000。

Subtask 2（35 分）：该子任务中不包含训练与合并操作。

Subtask 3（45 分）：此部分无额外限制条件。

输入格式： 按照题目描述提供输入数据。

输出格式： 根据题目要求输出对应结果。

输入样例：

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

提示说明： 前四次操作完成后，三支舰队中的飞船等级分别为 4、4、1 和 3。

执行第 5 次操作后，等级序列更新为 4、4、3、5。

第 6 次操作后，序列为 3、4、4、5。

第 7 次操作未产生任何变化。

第 8 次操作的查询结果为 4。

第 9 次操作后，序列变为 3、4、4、5、3。

第 10 次操作后，调整为 5、3、3、4、4。

第 11 次操作后，结果为 5、4、4。

第 12 次操作的返回值是 4。