{"problem":{"name":"[海淀区普及组 2025 T3] 炫耀预警器","description":{"content":"经过元旦联欢会的多项活动后，$n$ 名同学（编号从 1 到 $n$）都获得了一些积分，凑巧的是，第 $i$ 个同学的积分就是 $i$ 分。在接下来的 $q$ 个联欢项目中，每个项目都会增加一位同学的积分，具体来说，在第 $j(1 \\leq j \\leq q)$ 个项目结束后，第 $v_j$ 号同学的积分将变为 $n+j$ 分（因此暂时成为班里积分最高的人），该同学会一直保持新的积分，直到下一次该同","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4455"},"statements":[{"statement_type":"Markdown","content":"经过元旦联欢会的多项活动后，$n$ 名同学（编号从 1 到 $n$）都获得了一些积分，凑巧的是，第 $i$ 个同学的积分就是 $i$ 分。在接下来的 $q$ 个联欢项目中，每个项目都会增加一位同学的积分，具体来说，在第 $j(1 \\leq j \\leq q)$ 个项目结束后，第 $v_j$ 号同学的积分将变为 $n+j$ 分（因此暂时成为班里积分最高的人），该同学会一直保持新的积分，直到下一次该同学的积分被再次调整。\n\n有些同学之间经常彼此聊天，这可能会导致发生炫耀事件。具体来说，如果两个人 $a$ 和 $b$ 彼此聊天，并且 $a$ 的积分比 $b$ 高，那么 $a$ 会向 $b$ 炫耀自己的积分。一个“炫耀三元组”指的是三位学生 $a$、$b$ 和 $c$ 满足 $a$ 会向 $b$ 炫耀、$b$ 会向 $c$ 炫耀。\n\n老师不喜欢班里有太多同学互相炫耀，因此拜托你统计每个活动前后“炫耀三元组”的总数量。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$（$1 \\leq n \\leq 100000$，$0 \\leq m \\leq 100000$），分别表示同学人数和彼此聊天的关系对数。\n\n接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i(1 \\leq a_i < b_i \\leq n)$，表示学生 $a_i$ 和 $b_i$ 彼此聊天，每对关系只会出现一次。注意彼此聊天不具有传递性（即 $X$ 和 $Y$ 彼此聊天、$Y$ 和 $Z$ 彼此聊天不代表 $X$ 和 $Z$ 一定彼此聊天）。\n\n接下来一行包含一个整数 $q(0 \\leq q \\leq 100000)$，表示联欢项目的个数。接下来的 $q$ 行，每行包含一个整数 $v_j(1 \\leq v_j \\leq n)$，表示在第 $j$ 个联欢项目结束时，第 $v_j$ 号学生的积分将成为班级最高。\n\n## Output\n\n输出 $q+1$ 个整数，第 $i$ 个数表示在第 $i-1$ 个项目后班级中“炫耀三元组”的数量。注意输出的第一个数字是初始时的“炫耀三元组”数量。\n\n[samples]\n\n## Note\n\n数据范围：\n\n对于前 $30\\%$ 的数据，满足 $n,q \\le 500$；\n\n对于另外 $20\\%$ 的数据，满足 $q=0$；\n\n对于 $100\\%$ 的数据，满足“输入格式”中给出的数据范围。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4455","tags":["2025","北京","均摊分析","初中活动"],"sample_group":[["4 5\n1 2\n2 4\n1 3\n3 4\n2 3\n2\n2\n3","4\n3\n2"],["3 3\n1 2\n2 3\n1 3\n5\n1\n2\n2\n1\n3","1\n1\n1\n1\n1\n1"]],"created_at":"2026-03-03 11:09:25"}}