发帖
雷达卡
公司（company）- 清华大学
一家初创企业共有 n 名员工，员工编号从 1 到 n。每位员工 i 拥有一个确定的薪资值 ai。
初始状态下，所有员工均不了解其他同事的薪资情况。由于一次数据库故障，共泄露了 m 条信息，导致部分员工获知了其他员工的薪资数据。
对于员工 i，若其得知若干名员工的薪资，记其所了解人员的平均薪资为 vi（重复获取的信息也计入平均值计算），当满足条件 ai < vi 时，该员工将产生离职倾向。
若某员工未获取任何他人薪资信息，则不会产生离职想法。
现给出所有员工的薪资数组 ai，以及 m 组数据对 (xi, yi)，表示员工 xi 获悉了员工 yi 的薪资。请计算最终有多少员工会产生离职的想法。
输入格式
- 第一行输入两个正整数 n 和 m，分别代表公司总人数与泄露的数据条数。
- 第二行包含 n 个正整数，依次为每个员工的薪资 ai。
- 接下来 m 行，每行包含两个正整数 xi 和 yi，表示员工 xi 知晓了员工 yi 的薪资。
数据范围
所有测试数据满足：
- 3 ≤ n ≤ 10
- 1 ≤ m ≤ 2 × 10
- 1 ≤ ai ≤ 10
- 1 ≤ xi, yi ≤ n
输出格式
输出一个整数，表示产生离职想法的员工总数。
4 4
10 20 30 40
3 2
3 4
3 4
1 22飞船调度 - 清华大学
Gold Ship 正在进行一款太空即时战略游戏。游戏中存在 n 支舰队，每支舰队可容纳多艘飞船，每艘飞船具有一个等级（正整数）。
初始时，所有舰队均为空。玩家将执行 q 次操作，类型包括以下六种：
- 造船：给定参数 x, v，建造一艘等级为 v 的飞船，并将其加入第 x 支舰队。
- 训练：给定参数 x, v，使第 x 支舰队中所有飞船的等级提升 v 点。
- 移动：给定参数 x, y，将第 x 支舰队中任意一艘最低等级的飞船移动至第 y 支舰队。若该舰队为空，则无变化；若有多个同等级最低飞船，则任选其一移动。
- 查询：给定参数 x，返回第 x 支舰队中飞船等级的中位数。若舰队为空，则返回 0。
- 合并：给定参数 x, y，将第 x 支舰队的所有飞船全部转移至第 y 支舰队，原第 x 支舰队清空。
- 删除：给定参数 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。
京公网安备 11010802022788号
