Maximize Mex

题意翻译

# 题目 在一所学校里有 $n$ 名学生和 $m$ 个社团，社团被编号为 $1$~$m$ 。第 $i$ 个学生有一个能力值 $p_i$ ，且属于社团 $c_i$（每个学生恰好属于一个社团） 。 学校将要举行一个为期 $d$ 天的活动，每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中**各**选出一个人（如果某个社团没有人，就不选）组成一个队，令队里的学生的能力值的集合为 $S$，则该队的**总能力值**为 $mex(S)$ 。 > $mex(S)$ 表示 $S$ 中没有出现的最小的**非负**整数。例如： > >$mex(\{0,1,3,4\})=2;mex(\{1,2,3\})=0$ 但是由于学业繁忙，第 $i$ 天时，第 $k_i$ 个学生会离开社团（**在校长选这一天参加比赛的学生之前**）。 校长希望知道对于活动的每一天，他可能选出的队伍的总能力值最大是多少。 # 输入 第一行包括两个整数 $n,m$，分别是学生和社团的数量。 第二行包括 $n$ 个非负整数 $p_i$ ，表示第 $i$ 个学生的能力值。 第三行包括 $n$ 个正整数 $c_i$，表示第 $i$ 个学生所在的社团编号。 接下来输入一个整数 $d$，表示活动持续的天数。 接下来 $d$ 行，每行输入一个整数 $k_i$，表示第 $i$ 天学生 $d_i$ 离开社团。 # 输出 输出包括 $d$ 行，第 $i$ 行表示第 $i$ 天校长可能选出的队伍的最大总能力值。

题目描述

There are $ n $ students and $ m $ clubs in a college. The clubs are numbered from $ 1 $ to $ m $ . Each student has a potential $ p_i $ and is a member of the club with index $ c_i $ . Initially, each student is a member of exactly one club. A technical fest starts in the college, and it will run for the next $ d $ days. There is a coding competition every day in the technical fest. Every day, in the morning, exactly one student of the college leaves their club. Once a student leaves their club, they will never join any club again. Every day, in the afternoon, the director of the college will select one student from each club (in case some club has no members, nobody is selected from that club) to form a team for this day's coding competition. The strength of a team is the mex of potentials of the students in the team. The director wants to know the maximum possible strength of the team for each of the coming $ d $ days. Thus, every day the director chooses such team, that the team strength is maximized. The mex of the multiset $ S $ is the smallest non-negative integer that is not present in $ S $ . For example, the mex of the $ \{0, 1, 1, 2, 4, 5, 9\} $ is $ 3 $ , the mex of $ \{1, 2, 3\} $ is $ 0 $ and the mex of $ \varnothing $ (empty set) is $ 0 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq m \leq n \leq 5000 $ ), the number of students and the number of clubs in college. The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 0 \leq p_i < 5000 $ ), where $ p_i $ is the potential of the $ i $ -th student. The third line contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \leq c_i \leq m $ ), which means that $ i $ -th student is initially a member of the club with index $ c_i $ . The fourth line contains an integer $ d $ ( $ 1 \leq d \leq n $ ), number of days for which the director wants to know the maximum possible strength of the team. Each of the next $ d $ lines contains an integer $ k_i $ ( $ 1 \leq k_i \leq n $ ), which means that $ k_i $ -th student lefts their club on the $ i $ -th day. It is guaranteed, that the $ k_i $ -th student has not left their club earlier.

输出格式

For each of the $ d $ days, print the maximum possible strength of the team on that day.

输入输出样例

输入样例 #1

5 3
0 1 2 2 0
1 2 2 3 2
5
3
2
4
5
1

输出样例 #1

3
1
1
1
0

输入样例 #2

5 3
0 1 2 2 1
1 3 2 3 2
5
4
2
3
5
1

输出样例 #2

3
2
2
1
0

输入样例 #3

5 5
0 1 2 4 5
1 2 3 4 5
4
2
3
5
4

输出样例 #3

1
1
1
1

说明

Consider the first example: On the first day, student $ 3 $ leaves their club. Now, the remaining students are $ 1 $ , $ 2 $ , $ 4 $ and $ 5 $ . We can select students $ 1 $ , $ 2 $ and $ 4 $ to get maximum possible strength, which is $ 3 $ . Note, that we can't select students $ 1 $ , $ 2 $ and $ 5 $ , as students $ 2 $ and $ 5 $ belong to the same club. Also, we can't select students $ 1 $ , $ 3 $ and $ 4 $ , since student $ 3 $ has left their club. On the second day, student $ 2 $ leaves their club. Now, the remaining students are $ 1 $ , $ 4 $ and $ 5 $ . We can select students $ 1 $ , $ 4 $ and $ 5 $ to get maximum possible strength, which is $ 1 $ . On the third day, the remaining students are $ 1 $ and $ 5 $ . We can select students $ 1 $ and $ 5 $ to get maximum possible strength, which is $ 1 $ . On the fourth day, the remaining student is $ 1 $ . We can select student $ 1 $ to get maximum possible strength, which is $ 1 $ . On the fifth day, no club has students and so the maximum possible strength is $ 0 $ .

题意翻译

# 题目 在一所学校里有 $n$ 名学生和 $m$ 个社团，社团被编号为 $1$~$m$ 。第 $i$ 个学生有一个能力值 $p_i$ ，且属于社团 $c_i$（每个学生恰好属于一个社团） 。 学校将要举行一个为期 $d$ 天的活动，每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中**各**选出一个人（如果某个社团没有人，就不选）组成一个队，令队里的学生的能力值的集合为 $S$，则该队的**总能力值**为 $mex(S)$ 。 > $mex(S)$ 表示 $S$ 中没有出现的最小的**非负**整数。例如： > >$mex(\{0,1,3,4\})=2;mex(\{1,2,3\})=0$ 但是由于学业繁忙，第 $i$ 天时，第 $k_i$ 个学生会离开社团（**在校长选这一天参加比赛的学生之前**）。 校长希望知道对于活动的每一天，他可能选出的队伍的总能力值最大是多少。 # 输入 第一行包括两个整数 $n,m$，分别是学生和社团的数量。 第二行包括 $n$ 个非负整数 $p_i$ ，表示第 $i$ 个学生的能力值。 第三行包括 $n$ 个正整数 $c_i$，表示第 $i$ 个学生所在的社团编号。 接下来输入一个整数 $d$，表示活动持续的天数。 接下来 $d$ 行，每行输入一个整数 $k_i$，表示第 $i$ 天学生 $d_i$ 离开社团。 # 输出 输出包括 $d$ 行，第 $i$ 行表示第 $i$ 天校长可能选出的队伍的最大总能力值。