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$。 在此，我们将 evenness 定义如下。对于每个在 AtCoder 注册且有一个或多个婴儿的幼儿园，找出该幼儿园中评分最高的婴儿。evenness 定义为这些评分中的最小值。 对于每一次的 $Q$ 次转移，求出转移之后的 evenness。

输入格式

输入从标准输入以以下格式给出： $N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$ $C_1$ $D_1$ $C_2$ $D_2$ : $C_Q$ $D_Q$

输出格式

输出 $Q$ 行。 第 $j$ 行应包含第 $j$ 次转移之后的 evenness。

6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

6
2
6

2 2
4208 1234
3056 5678
1 2020
2 2020

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, 4$ 属于幼儿园 $1$，婴儿 $2, 5$ 属于幼儿园 $2$，婴儿 $3, 6$ 属于幼儿园 $3$。 在第 1 次转移使婴儿 $4$ 属于幼儿园 $3$ 之后，婴儿 $1$ 属于幼儿园 $1$，婴儿 $2, 5$ 属于幼儿园 $2$，婴儿 $3, 4, 6$ 属于幼儿园 $3$。幼儿园 $1, 2, 3$ 中评分最高的婴儿分别为 $8, 6, 9$。它们中的最小值是 $6$，因此输出的第 1 行应为 $6$。 在第 2 次转移使婴儿 $2$ 属于幼儿园 $1$ 之后，婴儿 $1, 2$ 属于幼儿园 $1$，婴儿 $5$ 属于幼儿园 $2$，婴儿 $3, 4, 6$ 属于幼儿园 $3$。幼儿园 $1, 2, 3$ 中评分最高的婴儿分别为 $8, 2, 9$。它们中的最小值是 $2$，因此输出的第 2 行应为 $2$。 在第 3 次转移使婴儿 $1$ 属于幼儿园 $2$ 之后，婴儿 $2$ 属于幼儿园 $1$，婴儿 $1, 5$ 属于幼儿园 $2$，婴儿 $3, 4, 6$ 属于幼儿园 $3$。幼儿园 $1, 2, 3$ 中评分最高的婴儿分别为 $6, 8, 9$。它们中的最小值是 $6$，因此输出的第 3 行应为 $6$。

标签: AtCoder|abc170E

来源

AtCoder|abc170E