AT_abc170_e [ABC170E] Smart Infants

题目描述

有 $N$ 名参加 AtCoder 的幼儿，每人编号为 $1$ 到 $N$。另外有 $2\times 10^5$ 所幼儿园，每所幼儿园编号为 $1$ 到 $2\times 10^5$。幼儿 $i$ 的评分为 $A_i$，最初属于幼儿园 $B_i$。

接下来会进行 $Q$ 次转园操作。在第 $j$ 次转园中，将幼儿 $C_j$ 的所属幼儿园更改为 $D_j$。

这里，“平等值”定义为：对于每个至少有一名幼儿的幼儿园，求出该园内评分最高的幼儿的评分，然后取这些评分中的最小值。

请你在每次转园操作后，输出当前的平等值。

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ $\ldots$ $A_N$ $B_N$ $C_1$ $D_1$ $C_2$ $D_2$ $\ldots$ $C_Q$ $D_Q$

输出格式

输出 $Q$ 行。第 $j$ 行输出第 $j$ 次转园操作后的平等值。

输入输出样例 #1

输入 #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 2
4208 1234
3056 5678
1 2020
2 2020

输出 #2

3056
4208

说明/提示

限制条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq C_j \leq N$
• $1 \leq B_i, D_j \leq 2 \times 10^5$
• 输入均为整数。
• 在第 $j$ 次转园操作前后，幼儿 $C_j$ 的所属幼儿园不同。

样例解释 1

最初，幼儿园 $1$ 有幼儿 $1, 4$，幼儿园 $2$ 有幼儿 $2, 5$，幼儿园 $3$ 有幼儿 $3, 6$。第 $1$ 次转园后，幼儿 $4$ 转到幼儿园 $3$，此时幼儿园 $1$ 有幼儿 $1$，幼儿园 $2$ 有幼儿 $2, 5$，幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 评分最高的幼儿为 $8$，幼儿园 $2$ 为 $6$，幼儿园 $3$ 为 $9$，这些中的最小值为 $6$，所以第 $1$ 行输出 $6$。第 $2$ 次转园后，幼儿 $2$ 转到幼儿园 $1$，此时幼儿园 $1$ 有幼儿 $1, 2$，幼儿园 $2$ 有幼儿 $5$，幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 评分最高为 $8$，幼儿园 $2$ 为 $2$，幼儿园 $3$ 为 $9$，最小值为 $2$，所以第 $2$ 行输出 $2$。第 $3$ 次转园后，幼儿 $1$ 转到幼儿园 $2$，此时幼儿园 $1$ 有幼儿 $2$，幼儿园 $2$ 有幼儿 $1, 5$，幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 评分最高为 $6$，幼儿园 $2$ 为 $8$，幼儿园 $3$ 为 $9$，最小值为 $6$，所以第 $3$ 行输出 $6$。

由 ChatGPT 4.1 翻译