公平
题目描述
有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。
联盟定期进行学员调院操作（共 Q 次）：第 j次操作将学员 Cj 调到学院 Dj。
联盟公平指数定义为：
对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。
请计算每次调院操作后的联盟公平指数。
输入格式
· 第一行：N Q
· 接下来 N 行：每行 Ai Bi，表示学员 ii 的能力值和初始学院
· 接下来 Q 行：每行 Cj Dj，表示将学员 Cj 调到学院 Dj
输出格式
· Q 行：每行一个整数，表示每次操作后的公平指数
输入样例#1
6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2
输出样例#1
6
2
6
输入样例#2
2 2
4208 1234
3056 5678
1 2020
2 2020
输出样例#2
3056
4208
说明提示
1≤N,Q≤2×105，1≤N,Q≤2×105
1≤Ai≤109，1≤Ai≤109
1≤Cj≤N，1≤Cj≤N
1≤Bi,Dj≤2×105，1≤Bi,Dj≤2×105
输入均为整数
每次转园操作会改变所属学院
限制
时间限制：1000ms
内存限制：256MiB
相似题推荐
专属教室
题目描述
在一所学校中，有 N 个班级，每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si，但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同，所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室，且一次只能安排一个班级进行更换。在更换时，目标教室必须是空闲的。
学校希望找到一个合理的更换顺序，使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行，每行两个字符串 Si 和 Ti，表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换，输出 Yes，否则输出 No。
输入样例#1
2 b m m d
输出样例#1
Yes
输入样例#2
3 a b b c c a
输出样例#2
No
说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串，长度在 1 到 8 之间。
Si≠Ti
所有 Si 互不相同。
所有 Ti 互不相同。
限制
时间限制：1000ms
内存限制：256MiB
