[海淀区普及组 2025 T3] 炫耀预警器

Luogu
IDLGB4455
Time4000ms
Memory512MB
DifficultyP5
2025北京均摊分析初中活动
经过元旦联欢会的多项活动后,$n$ 名同学(编号从 1 到 $n$)都获得了一些积分,凑巧的是,第 $i$ 个同学的积分就是 $i$ 分。在接下来的 $q$ 个联欢项目中,每个项目都会增加一位同学的积分,具体来说,在第 $j(1 \leq j \leq q)$ 个项目结束后,第 $v_j$ 号同学的积分将变为 $n+j$ 分(因此暂时成为班里积分最高的人),该同学会一直保持新的积分,直到下一次该同学的积分被再次调整。 有些同学之间经常彼此聊天,这可能会导致发生炫耀事件。具体来说,如果两个人 $a$ 和 $b$ 彼此聊天,并且 $a$ 的积分比 $b$ 高,那么 $a$ 会向 $b$ 炫耀自己的积分。一个“炫耀三元组”指的是三位学生 $a$、$b$ 和 $c$ 满足 $a$ 会向 $b$ 炫耀、$b$ 会向 $c$ 炫耀。 老师不喜欢班里有太多同学互相炫耀,因此拜托你统计每个活动前后“炫耀三元组”的总数量。 ## Input 第一行包含两个整数 $n$ 和 $m$($1 \leq n \leq 100000$,$0 \leq m \leq 100000$),分别表示同学人数和彼此聊天的关系对数。 接下来的 $m$ 行,每行包含两个整数 $a_i$ 和 $b_i(1 \leq a_i < b_i \leq n)$,表示学生 $a_i$ 和 $b_i$ 彼此聊天,每对关系只会出现一次。注意彼此聊天不具有传递性(即 $X$ 和 $Y$ 彼此聊天、$Y$ 和 $Z$ 彼此聊天不代表 $X$ 和 $Z$ 一定彼此聊天)。 接下来一行包含一个整数 $q(0 \leq q \leq 100000)$,表示联欢项目的个数。接下来的 $q$ 行,每行包含一个整数 $v_j(1 \leq v_j \leq n)$,表示在第 $j$ 个联欢项目结束时,第 $v_j$ 号学生的积分将成为班级最高。 ## Output 输出 $q+1$ 个整数,第 $i$ 个数表示在第 $i-1$ 个项目后班级中“炫耀三元组”的数量。注意输出的第一个数字是初始时的“炫耀三元组”数量。 [samples] ## Note 数据范围: 对于前 $30\%$ 的数据,满足 $n,q \le 500$; 对于另外 $20\%$ 的数据,满足 $q=0$; 对于 $100\%$ 的数据,满足“输入格式”中给出的数据范围。
Samples
Input #1
4 5
1 2
2 4
1 3
3 4
2 3
2
2
3
Output #1
4
3
2
Input #2
3 3
1 2
2 3
1 3
5
1
2
2
1
3
Output #2
1
1
1
1
1
1
API Response (JSON)
{
  "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$ 分(因此暂时成为班里积分最高的人),该同学会一直保持新的积分,直到下一次该同...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments