贡献名单

想法	标程	数据	验题	题解
船酱魔王			035966_L3	船酱魔王

题目描述

随着 B 市中考招生方式的多元化，中考统招的名额数量日益减少，在本题目中，你需要根据平行志愿的招生原则（我们会给出详细的解释），高效模拟这一过程。

小 $\zeta$ 为了更好的填报志愿，找到了某年的中考志愿填报和录取的情况。

具体地，$n$ 位学生第 $i$ 个人会填报 $l_i$ 个志愿，即 $l_i$ 所学校。第 $i$ 个人的第 $j$ 志愿为学校 $a_{i,j}$。总共有 $m$ 所参与招生的学校，第 $i$ 所提供了 $t_i$ 个名额。

按照以下流程确认每个人的录取情况，记 $b_i$ 为学校 $i$ 已经招生人数：

• 找到所有目前未确定录取结果的最高分学生；
• 设未招满学校集合 $S=\{i \mid i \in [1,m] \land t_i > b_i\}$；
• 对于每个当前的最高分学生 $x$，从第一志愿到最后志愿枚举学校 $i=a_{x,1},a_{x,2},\cdots,a_{x,l_x}$：
  • 如果 $i\in S$，则学生 $x$ 被学校 $i$ 录取，令 $b_i\gets b_i+1$，结束；否则，继续枚举下一个。
  • 若枚举所有 $i$ 后没有结束，则学生 $x$ 不被任何学校录取。
• 在上一步中 $b_i$ 改变不会改变 $S$，即可能会出现一些学校 $b_i>t_i$。无论有没有被录取，这些学生的录取结果都确定了。

对于一次询问，格式如下：

• x v：永久性改变 $t_x \leftarrow t_x-v$，输出录取结果变化的学生个数。

输入格式

第一行三个整数 $n,m,q$，代表学生人数、学校个数和询问次数。

接下来一行，$m$ 个整数，第 $i$ 个整数 $t_i$ 代表高中校 $i$ 的招生名额数。

接下来 $n$ 行，第 $i$ 行第一个整数 $l_i$ 代表学生 $i$ 的志愿填报个数，接下来 $l_i$ 个整数依次代表这位学生的第一至最后志愿高中校，最后一个整数 $o_i$ 表示学生 $i$ 的中考分数。

接下来 $q$ 行，每行均为 x v 格式，代表一次询问，含义详见题目描述。

输出格式

$q$ 行，每行一个整数代表录取结果改变的学生数量。

输入输出样例 #1

输入 #1

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

输出 #1

0
0
2
2
3

说明/提示

【样例解释 #1】

初始时，录取结果分别为（$0$ 表示未被任何学校录取）$\{1,2,3,3,3\}$。

前两次操作后，录取结果不变。

第三次操作后，录取结果分别为 $\{1,2,3,2,0\}$。

第四次操作后，录取结果分别为 $\{1,0,2,2,0\}$。

第五次操作后，录取结果分别为 $\{0,0,1,0,0\}$。

【数据规模与约定】

对于 $100\%$ 的数据：

• $1 \le n,m,q \le 3 \times 10^5$，$0 \le t_i \le 10^6$，$0 \le l_i \le m$，$\sum l_i \le 10^6$，$1 \le a_{i,j} \le m$，$0 \le o_i \le 10^6$；
• 对于同一个 $i$ 不保证 $a_{i,j}$ 互不相同；
• 对于每次操作有 $1 \le x \le m$ 和 $0 \le v \le 10^6$，操作后保证 $t_i \ge 0$。

提示：本题开启捆绑测试。

• Subtask 1（15 pts）：$n,m,q \le 500$，$\sum l_i \le 5000$。
• Subtask 2（20 pts）：$o_i$ 只有两种取值。
• Subtask 3（35 pts）：所有的 $o_i$ 互异。
• Subtask 4（30 pts）：无特殊限制。